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

假设我正在使用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主题中搜索Groovy的答案,下面是如何在Groovy中做到这一点:

dev map = new HashMap<String, Integer>()
map.put("key1", 3)

map.merge("key1", 1) {a, b -> a + b}
map.merge("key2", 1) {a, b -> a + b}

其他回答

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

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)相比,开销不应该那么多。

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

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

我不知道它有多高效,但下面的代码也可以工作。你需要在开头定义一个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

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

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

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