我希望这个问题对这个论坛来说不是太基本的,但我们会看到的。我想知道如何重构一些代码以获得更好的性能,这是运行了很多次。

假设我正在使用Map(可能是HashMap)创建一个词频列表,其中每个键都是一个包含要统计的单词的String,值是一个Integer,该Integer在每次找到单词的标记时递增。

在Perl中,增加这样一个值非常简单:

$map{$word}++;

但在Java中,这要复杂得多。下面是我目前的做法:

int count = map.containsKey(word) ? map.get(word) : 0;
map.put(word, count + 1);

这当然依赖于新Java版本中的自动装箱特性。我想知道您是否可以建议一种更有效的方法来增加这个值。是否有更好的性能理由避开Collections框架而使用其他框架呢?

更新:我已经对几个答案做了测试。见下文。


当前回答

MutableInt方法的一个变体可能更快,如果有点hack,是使用一个单元素int数组:

Map<String,int[]> map = new HashMap<String,int[]>();
...
int[] value = map.get(key);
if (value == null) 
  map.put(key, new int[]{1} );
else
  ++value[0];

如果您可以使用此变体重新运行性能测试,那将非常有趣。这可能是最快的。


编辑:上面的模式对我来说很好,但最终我改变使用Trove的集合来减少我正在创建的一些非常大的地图的内存大小——作为奖励,它也更快。

一个非常好的特性是TObjectIntHashMap类有一个单独的adjustOrPutValue调用,根据该键是否已经有一个值,它将放置一个初始值或增加现有值。这对于增量来说是完美的:

TObjectIntHashMap<String> map = new TObjectIntHashMap<String>();
...
map.adjustOrPutValue(key, 1, 1);

其他回答

部分测试结果

对于这个问题,我已经得到了很多很好的答案——谢谢大家——所以我决定进行一些测试,找出哪种方法实际上是最快的。我测试的五个方法是:

我在问题中提到的“ContainsKey”方法 Aleksandar Dimitrov建议的“TestForNull”方法 Hank Gay建议的“AtomicLong”方法 即鲁道夫提出的“宝藏”方法 phax.myopenid.com建议的“MutableInt”方法

方法

我是这么做的……

created five classes that were identical except for the differences shown below. Each class had to perform an operation typical of the scenario I presented: opening a 10MB file and reading it in, then performing a frequency count of all the word tokens in the file. Since this took an average of only 3 seconds, I had it perform the frequency count (not the I/O) 10 times. timed the loop of 10 iterations but not the I/O operation and recorded the total time taken (in clock seconds) essentially using Ian Darwin's method in the Java Cookbook. performed all five tests in series, and then did this another three times. averaged the four results for each method.

结果

我将首先展示结果,并为感兴趣的人提供下面的代码。

正如预期的那样,ContainsKey方法是最慢的,因此我将给出每个方法的速度与该方法的速度的比较。

ContainsKey: 30.654秒(基线) AtomicLong: 29.780秒(速度的1.03倍) TestForNull: 28.804秒(1.06倍) Trove: 26.313秒(快1.16倍) MutableInt: 25.747秒(1.19倍)

结论

似乎只有MutableInt方法和Trove方法明显更快,因为只有它们的性能提升超过10%。然而,如果线程是一个问题,AtomicLong可能比其他的更有吸引力(我不确定)。我还用final变量运行了TestForNull,但是差别可以忽略不计。

注意,我没有分析不同场景中的内存使用情况。我很高兴听到任何人对MutableInt和Trove方法如何可能影响内存使用有很好的见解。

就我个人而言,我觉得MutableInt方法最有吸引力,因为它不需要加载任何第三方类。因此,除非我发现它有问题,否则我很可能会走这条路。

的代码

下面是每个方法的关键代码。

ContainsKey

import java.util.HashMap;
import java.util.Map;
...
Map<String, Integer> freq = new HashMap<String, Integer>();
...
int count = freq.containsKey(word) ? freq.get(word) : 0;
freq.put(word, count + 1);

测试空

import java.util.HashMap;
import java.util.Map;
...
Map<String, Integer> freq = new HashMap<String, Integer>();
...
Integer count = freq.get(word);
if (count == null) {
    freq.put(word, 1);
}
else {
    freq.put(word, count + 1);
}

AtomicLong

import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentMap;
import java.util.concurrent.atomic.AtomicLong;
...
final ConcurrentMap<String, AtomicLong> map = 
    new ConcurrentHashMap<String, AtomicLong>();
...
map.putIfAbsent(word, new AtomicLong(0));
map.get(word).incrementAndGet();

宝库

import gnu.trove.TObjectIntHashMap;
...
TObjectIntHashMap<String> freq = new TObjectIntHashMap<String>();
...
freq.adjustOrPutValue(word, 1, 1);

MutableInt

import java.util.HashMap;
import java.util.Map;
...
class MutableInt {
  int value = 1; // note that we start at 1 since we're counting
  public void increment () { ++value;      }
  public int  get ()       { return value; }
}
...
Map<String, MutableInt> freq = new HashMap<String, MutableInt>();
...
MutableInt count = freq.get(word);
if (count == null) {
    freq.put(word, new MutableInt());
}
else {
    count.increment();
}

MutableInt方法的一个变体可能更快,如果有点hack,是使用一个单元素int数组:

Map<String,int[]> map = new HashMap<String,int[]>();
...
int[] value = map.get(key);
if (value == null) 
  map.put(key, new int[]{1} );
else
  ++value[0];

如果您可以使用此变体重新运行性能测试,那将非常有趣。这可能是最快的。


编辑:上面的模式对我来说很好,但最终我改变使用Trove的集合来减少我正在创建的一些非常大的地图的内存大小——作为奖励,它也更快。

一个非常好的特性是TObjectIntHashMap类有一个单独的adjustOrPutValue调用,根据该键是否已经有一个值,它将放置一个初始值或增加现有值。这对于增量来说是完美的:

TObjectIntHashMap<String> map = new TObjectIntHashMap<String>();
...
map.adjustOrPutValue(key, 1, 1);

希望我正确理解了你的问题,我从Python来到Java,所以我可以同情你的挣扎。

如果你有

map.put(key, 1)

你会这么做

map.put(key, map.get(key) + 1)

希望这能有所帮助!

我不知道它有多高效,但下面的代码也可以工作。你需要在开头定义一个bifuncfunction。另外,你可以用这个方法做更多的增量。

public static Map<String, Integer> strInt = new HashMap<String, Integer>();

public static void main(String[] args) {
    BiFunction<Integer, Integer, Integer> bi = (x,y) -> {
        if(x == null)
            return y;
        return x+y;
    };
    strInt.put("abc", 0);


    strInt.merge("abc", 1, bi);
    strInt.merge("abc", 1, bi);
    strInt.merge("abc", 1, bi);
    strInt.merge("abcd", 1, bi);

    System.out.println(strInt.get("abc"));
    System.out.println(strInt.get("abcd"));
}

输出是

3
1
Map<String, Integer> map = new HashMap<>();
String key = "a random key";
int count = map.getOrDefault(key, 0); // ensure count will be one of 0,1,2,3,...
map.put(key, count + 1);

这就是用简单代码增加值的方法。

好处:

不需要添加一个新类或使用可变int的另一个概念 不依赖于任何库 容易理解到底发生了什么(没有太多抽象)

缺点:

将在哈希映射中搜索get()和put()两次。所以它不是性能最好的代码。

从理论上讲,一旦调用get(),您就已经知道在哪里放置(),因此不需要再次搜索。但是在哈希映射中搜索通常只需要很短的时间你可以忽略这个性能问题。

但如果你对这个问题非常认真,你是一个完美主义者,另一种方法是使用合并方法,这(可能)比前面的代码片段更有效,因为你将(理论上)只搜索一次地图:(虽然这段代码乍一看不明显,但它是简短的和性能)

map.merge(key, 1, (a,b) -> a+b);

建议:在大多数情况下,你应该更关心代码的可读性,而不是性能的提高。如果第一个代码片段更容易理解,那么就使用它。但如果你能很好地理解第二个,那么你也可以去做!