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

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

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


当前回答

在java 8中,简单易行的方法如下:

final ConcurrentMap<String, AtomicLong> map = new ConcurrentHashMap<String, AtomicLong>();
    map.computeIfAbsent("foo", key -> new AtomicLong(0)).incrementAndGet();

其他回答

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);

函数Java库的TreeMap数据结构在最新的主干头中有一个更新方法:

public TreeMap<K, V> update(final K k, final F<V, V> f)

使用示例:

import static fj.data.TreeMap.empty;
import static fj.function.Integers.add;
import static fj.pre.Ord.stringOrd;
import fj.data.TreeMap;

public class TreeMap_Update
  {public static void main(String[] a)
    {TreeMap<String, Integer> map = empty(stringOrd);
     map = map.set("foo", 1);
     map = map.update("foo", add.f(1));
     System.out.println(map.get("foo").some());}}

这个程序输出“2”。

如果您正在使用Eclipse Collections,则可以使用HashBag。在内存使用方面,这将是最有效的方法,而且在执行速度方面也会表现良好。

HashBag由MutableObjectIntMap支持,MutableObjectIntMap存储基本整数而不是Counter对象。这减少了内存开销并提高了执行速度。

HashBag提供了您需要的API,因为它是一个集合,还允许您查询条目的出现次数。

下面是一个来自Eclipse Collections Kata的例子。

MutableBag<String> bag =
  HashBag.newBagWith("one", "two", "two", "three", "three", "three");

Assert.assertEquals(3, bag.occurrencesOf("three"));

bag.add("one");
Assert.assertEquals(2, bag.occurrencesOf("one"));

bag.addOccurrences("one", 4);
Assert.assertEquals(6, bag.occurrencesOf("one"));

注意:我是Eclipse Collections的提交者。

作为我自己评论的后续:Trove看起来是可行的。如果出于某种原因,您希望坚持使用标准JDK,那么ConcurrentMap和AtomicLong可以使代码稍微好一点,不过使用YMMV。

    final ConcurrentMap<String, AtomicLong> map = new ConcurrentHashMap<String, AtomicLong>();
    map.putIfAbsent("foo", new AtomicLong(0));
    map.get("foo").incrementAndGet();

将在foo的map中保留1作为值。实际上,增加线程的友好性是这种方法所推荐的。

可以使用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,但代价是更高的空间消耗。