用Java增加Map值的最有效方法



Answers

好的,可能是一个老问题,但Java 8有一个较短的方法:

Map.merge(key, 1, Integer::sum)

它做什么:如果密钥不存在,则将1作为值,否则将1与链接到密钥的值相加 。 更多信息here

Question

我希望这个问题不被视为这个论坛的基础,但我们会看到。 我想知道如何重构一些代码以获得更好的性能,而这些代码正在运行很多次。

假设我使用一个Map(可能是一个HashMap)创建一个词频列表,其中每个键都是一个字符串,并且该字符被计数,并且该值是一个整数,每当找到该单词的一个标记时该值就会递增。

在Perl中,递增这样一个值将非常简单:

$map{$word}++;

但在Java中,它更复杂。 这是我目前正在做的事情:

int count = map.containsKey(word) ? map.get(word) : 0;
map.put(word, count + 1);

这当然依赖于较新Java版本中的自动装箱功能。 我想知道你是否可以提出一种更有效的方式来增加这种价值。 是否有避免使用Collections框架和使用其他方法的良好性能原因?

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




你确定这是一个瓶颈吗? 你有没有做过任何性能分析?

尝试使用NetBeans Profiler(其免费并内置到NB 6.1中)来查看热点。

最后,JVM升级(比如从1.5-> 1.6)通常是一种便宜的性能增强器。 即使内部版本号升级也可以提供良好的性能提升。 如果您在Windows上运行并且这是服务器类应用程序,请在命令行上使用-server来使用服务器热点JVM。 在Linux和Solaris机器上,这是自动检测的。




我认为你的解决方案将是标准方式,但是 - 正如你自己所指出的 - 这可能不是最快的方式。

你可以看看GNU Trove 。 这是一个包含各种快速原始集合的库。 你的例子会使用一个TObjectIntHashMap,它有一个方法adjustOrPutValue,它正是你想要的。




查看Google Collections Library以了解这种情况总是一个好主意。 在这种情况下, Multiset可以做到这一点:

Multiset bag = Multisets.newHashMultiset();
String word = "foo";
bag.add(word);
bag.add(word);
System.out.println(bag.count(word)); // Prints 2

有迭代键/条目等Map-like方法,内部实现当前使用HashMap<E, AtomicInteger> ,所以你不会产生装箱成本。




Google Collections HashMultiset:
- 使用起来非常优雅
- 但消耗CPU和内存

最好的办法是像这样: Entry<K,V> getOrPut(K); (优雅,低成本)

这种方法只会计算散列和索引一次,然后我们可以用条目来做我们想要的(替换或更新值)。

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




Functional Java库的TreeMap结构在最新的中继头中有一个update方法:

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”。




我不知道它的效率如何,但下面的代码也可以工作。你需要在开头定义一个BiFunction 。 另外,你可以使用这种方法做更多的事情。

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



各种原始包装,例如Integer是不可改变的,所以除非你可以像AtomicLong那样做, 否则真的没有更简洁的方法去做你正在问的东西。 我可以在一分钟内给出一个结果并更新。 顺便说一下, Hashtable 集合框架的一部分。




@Hank Gay

作为我自己的(相当无用的)评论的后续:Trove看起来像要走的路。 如果不管什么原因,你想坚持使用标准的JDK, ConcurrentMapAtomicLong可以使代码更好一点,虽然YMMV。

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

将在foo的地图中留下1作为值。 实际上,线程的友好性增加是这种方法必须推荐的。




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

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))。 虽然垃圾收集器非常有效地处理短暂的对象,但性能会受到一定程度的影响。

如果你知道所做增量的数量将远远超过键的数量(在这种情况下=字),请考虑使用int保持器。 Phax已经为此提供了代码。 这里又有两个变化(持有者类设置为静态和初始值设置为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

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




如果您使用Eclipse集合 ,则可以使用HashBag 。 这将是内存使用方面最有效的方法,并且在执行速度方面也会表现出色。

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

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

下面是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集合的提交者。




Links