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

假设我正在使用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框架而使用其他框架呢?

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


当前回答

番石榴是你的朋友…

...至少在某些情况下是这样。他们有这个很好的AtomicLongMap。特别好,因为你在地图上处理的是长值。

E.g.

AtomicLongMap<String> map = AtomicLongMap.create();
[...]
map.getAndIncrement(word);

也可以在值上增加多于1的值:

map.getAndAdd(word, 112L); 

其他回答

番石榴是你的朋友…

...至少在某些情况下是这样。他们有这个很好的AtomicLongMap。特别好,因为你在地图上处理的是长值。

E.g.

AtomicLongMap<String> map = AtomicLongMap.create();
[...]
map.getAndIncrement(word);

也可以在值上增加多于1的值:

map.getAndAdd(word, 112L); 

2016年一点研究:https://github.com/leventov/java-word-count,基准源代码

每种方法的最佳效果(越小越好):

                 time, ms
kolobokeCompile  18.8
koloboke         19.8
trove            20.8
fastutil         22.7
mutableInt       24.3
atomicInteger    25.3
eclipse          26.9
hashMap          28.0
hppc             33.6
hppcRt           36.5

时间、空间的结果:

“put”需要“get”(以确保没有重复的密钥)。 所以直接做一个"看跌" 如果之前有一个值,那么做加法:

Map map = new HashMap ();

MutableInt newValue = new MutableInt (1); // default = inc
MutableInt oldValue = map.put (key, newValue);
if (oldValue != null) {
  newValue.add(oldValue); // old + inc
}

如果count从0开始,则添加1:(或任何其他值…)

Map map = new HashMap ();

MutableInt newValue = new MutableInt (0); // default
MutableInt oldValue = map.put (key, newValue);
if (oldValue != null) {
  newValue.setValue(oldValue + 1); // old + inc
}

注意:这段代码不是线程安全的。使用它来构建然后使用映射,而不是并发地更新它。

优化:在一个循环中,保留旧值成为下一个循环的新值。

Map map = new HashMap ();
final int defaut = 0;
final int inc = 1;

MutableInt oldValue = new MutableInt (default);
while(true) {
  MutableInt newValue = oldValue;

  oldValue = map.put (key, newValue); // insert or...
  if (oldValue != null) {
    newValue.setValue(oldValue + inc); // ...update

    oldValue.setValue(default); // reuse
  } else
    oldValue = new MutableInt (default); // renew
  }
}

可以使用Java 8提供的Map接口中的computeIfAbsent方法。

final Map<String,AtomicLong> map = new ConcurrentHashMap<>();
map.computeIfAbsent("A", k->new AtomicLong(0)).incrementAndGet();
map.computeIfAbsent("B", k->new AtomicLong(0)).incrementAndGet();
map.computeIfAbsent("A", k->new AtomicLong(0)).incrementAndGet(); //[A=2, B=1]

方法computeIfAbsent检查指定的键是否已经与某个值关联?如果没有关联值,则尝试使用给定的映射函数计算其值。在任何情况下,它都会返回与指定键关联的当前值(现有值或计算值),如果计算值为空则返回null。

另一方面,如果你遇到多个线程更新一个公共和的情况,你可以看看LongAdder类。在高争用情况下,该类的预期吞吐量显著高于AtomicLong,但代价是更高的空间消耗。

谷歌集合HashMultiset: -使用起来相当优雅 —但会消耗CPU和内存

最好是有这样一个方法:Entry<K,V> getOrPut(K); (美观,成本低)

这样的方法只计算哈希和索引一次, 然后我们可以对元素做我们想做的 (替换或更新值)。

更优雅: -取一个HashSet<Entry> -扩展它,以便get(K)在需要时放置一个新的条目 -入口可以是你自己的对象。 ——> (new MyHashSet()).get(k).increment();