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

假设我正在使用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); 

其他回答

我将使用Apache Collections Lazy Map(将值初始化为0),并使用Apache Lang中的MutableIntegers作为该映射中的值。

在您的方法中,最大的代价是必须搜索两次地图。在我这里,你只需要做一次。只需要获取值(如果没有,它将被初始化)并增加它。

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

内存旋转在这里可能是一个问题,因为对大于或等于128的int进行装箱都会导致对象分配(参见Integer.valueOf(int))。尽管垃圾收集器非常有效地处理存在时间很短的对象,但性能会在一定程度上受到影响。

如果您知道增量的数量将大大超过键的数量(在本例中为=words),请考虑使用int holder。Phax已经为此提供了代码。这里又是一次,有两个变化(holder类是静态的,初始值设置为1):

static class MutableInt {
  int value = 1;
  void inc() { ++value; }
  int get() { return value; }
}
...
Map<String,MutableInt> map = new HashMap<String,MutableInt>();
MutableInt value = map.get(key);
if (value == null) {
  value = new MutableInt();
  map.put(key, value);
} else {
  value.inc();
}

如果需要极致的性能,请寻找直接针对基本值类型定制的Map实现。jrudolph提到了GNU Trove。

顺便说一下,这个主题的一个很好的搜索词是“直方图”。

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

如果你有

map.put(key, 1)

你会这么做

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

希望这能有所帮助!

我建议使用Java 8 Map::compute()。 它也考虑键不存在的情况。

Map.compute(num, (k, v) -> (v == null) ? 1 : v + 1);