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

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

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


当前回答

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

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

其他回答

你应该意识到你最初的尝试

int count = map.containsKey(word) ? map.get(word) : 0;

包含映射上两个可能代价高昂的操作,即containsKey和get。前者执行的操作可能与后者非常相似,因此您要做两次相同的工作!

如果查看Map的API,当Map不包含所请求的元素时,get操作通常返回null。

注意,这将得到一个像

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

dangerous, since it might yield NullPointerExceptions. You should check for a null first. Also note, and this is very important, that HashMaps can contain nulls by definition. So not every returned null says "there is no such element". In this respect, containsKey behaves differently from get in actually telling you whether there is such an element. Refer to the API for details. For your case, however, you might not want to distinguish between a stored null and "noSuchElement". If you don't want to permit nulls you might prefer a Hashtable. Using a wrapper library as was already proposed in other answers might be a better solution to manual treatment, depending on the complexity of your application. To complete the answer (and I forgot to put that in at first, thanks to the edit function!), the best way of doing it natively, is to get into a final variable, check for null and put it back in with a 1. The variable should be final because it's immutable anyway. The compiler might not need this hint, but its clearer that way. final HashMap map = generateRandomHashMap(); final Object key = fetchSomeKey(); final Integer i = map.get(key); if (i != null) { map.put(i + 1); } else { // do something } If you do not want to rely on autoboxing, you should say something like map.put(new Integer(1 + i.getValue())); instead.

另一种方法是创建一个可变整数:

class MutableInt {
  int value = 0;
  public void inc () { ++value; }
  public 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 ();
}

当然,这意味着创建一个额外的对象,但与创建一个Integer(即使是Integer. valueof)相比,开销不应该那么多。

使用流和getOrDefault计数:

String s = "abcdeff";
s.chars().mapToObj(c -> (char) c)
 .forEach(c -> {
     int count = countMap.getOrDefault(c, 0) + 1;
     countMap.put(c, count);
  });

内存旋转在这里可能是一个问题,因为对大于或等于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。

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

作为我自己评论的后续: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作为值。实际上,增加线程的友好性是这种方法所推荐的。