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




mongodb mapreduce (17)

一些测试结果

我已经得到了很多这个问题的好答案 - 谢谢大家 - 所以我决定运行一些测试并找出哪种方法实际上是最快的。 我测试的五种方法是:

  • 我在问题中提出的“ContainsKey”方法
  • Aleksandar Dimitrov建议的“TestForNull”方法
  • Hank Gay提出的“AtomicLong”方法
  • jrudolph建议的“Trove”方法
  • phax.myopenid.com建议的“MutableInt”方法

方法

这就是我所做的...

  1. 创建了五个类,除了下面显示的差异之外,它们是相同的。 每个课程都必须执行我提供的场景中典型的操作:打开一个10MB文件并读入,然后执行文件中所有单词记号的频率计数。 由于这平均只需要3秒,所以我执行了10次频率计数(而不是I / O)。
  2. 对10次迭代的循环进行计时,但不对I / O操作进行计时,并记录基本上使用Java Cookbook中的Ian Darwin方法所花费的总时间(以时钟秒为单位)。
  3. 连续进行所有五项测试,然后再做三次。
  4. 平均每种方法的四个结果。

结果

我将首先介绍结果以及下面的代码,供有兴趣的人参考。

正如所料, ContainsKey方法是最慢的,所以我会将每种方法的速度与该方法的速度进行比较。

  • ContainsKey: 30.654秒(基线)
  • AtomicLong: 29.780秒(1.03倍)
  • TestForNull: 28.804秒(1.06倍)
  • 特洛夫 26.313秒(1.16倍)
  • MutableInt: 25.747秒(1.19倍)

结论

看来只有MutableInt方法和Trove方法明显更快,因为只有它们的性能提升超过10%。 但是,如果线程是一个问题,AtomicLong可能比其他人更有吸引力(我不太确定)。 我也用final变量运行TestForNull,但差异可以忽略不计。

请注意,我没有在不同情况下分析内存使用情况。 我很乐意听到任何对MutableInt和Trove方法可能会影响内存使用情况的人有很好的见解。

就个人而言,我发现MutableInt方法最具吸引力,因为它不需要加载任何第三方类。 所以除非我发现问题,否则这就是我最可能去的方式。

代码

这是每种方法的关键代码。

的containsKey

import java.util.HashMap;
import java.util.Map;
...
Map<String, Integer> freq = new HashMap<String, Integer>();
...
int count = freq.containsKey(word) ? freq.get(word) : 0;
freq.put(word, count + 1);

TestForNull

import java.util.HashMap;
import java.util.Map;
...
Map<String, Integer> freq = new HashMap<String, Integer>();
...
Integer count = freq.get(word);
if (count == null) {
    freq.put(word, 1);
}
else {
    freq.put(word, count + 1);
}

的AtomicLong

import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentMap;
import java.util.concurrent.atomic.AtomicLong;
...
final ConcurrentMap<String, AtomicLong> map = 
    new ConcurrentHashMap<String, AtomicLong>();
...
map.putIfAbsent(word, new AtomicLong(0));
map.get(word).incrementAndGet();

特罗韦

import gnu.trove.TObjectIntHashMap;
...
TObjectIntHashMap<String> freq = new TObjectIntHashMap<String>();
...
freq.adjustOrPutValue(word, 1, 1);

MutableInt

import java.util.HashMap;
import java.util.Map;
...
class MutableInt {
  int value = 1; // note that we start at 1 since we're counting
  public void increment () { ++value;      }
  public int  get ()       { return value; }
}
...
Map<String, MutableInt> freq = new HashMap<String, MutableInt>();
...
MutableInt count = freq.get(word);
if (count == null) {
    freq.put(word, new MutableInt());
}
else {
    count.increment();
}

https://code.i-harness.com

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

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

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

$map{$word}++;

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

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

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

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


谷歌Guava是你的朋友...

......至少在某些情况下。 他们有这个不错的AtomicLongMap 。 特别好,因为你在地图上处理的价值很高。

例如

AtomicLongMap map = AtomicLongMap.create();
[...]
map.getAndIncrement(word);

也可以添加1以上的值:

map.getAndAdd(word, new Long(112)); 


@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作为值。 实际上,线程的友好性增加是这种方法必须推荐的。


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

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

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

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


MutableInt方法的一个变体可能会更快,如果有点破解的话,就是使用单元素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的集合来减少我创建的一些非常大的地图中的内存大小 - 作为奖励,它也更快。

一个非常好的特性是adjustOrPutValue类有一个adjustOrPutValue调用,根据该键是否已经有一个值,将调用初始值或递增现有值。 这对于递增是完美的:

TObjectIntHashMap<String> map = new TObjectIntHashMap<String>();
...
map.adjustOrPutValue(key, 1, 1);

你应该知道你最初的尝试

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

在地图上包含两个潜在的昂贵操作,即containsKeyget 。 前者执行的操作可能与后者非常相似,所以你要做两次相同的工作!

如果您查看Map的API,则当地图不包含请求的元素时, get操作通常会返回null

请注意,这将会产生类似的解决方案

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

危险的,因为它可能产生NullPointerException 。 你应该首先检查null

还要注意 ,这非常重要, HashMap 可以按照定义包含nulls 。 因此,不是每个返回的null表示“没有这样的元素”。 在这方面, containsKey行为不同于实际告诉你是否存在这样的元素。 有关详细信息,请参阅API。

但是,对于您的情况,您可能不想区分存储的null和“noSuchElement”。 如果你不想允许null你可能更喜欢一个Hashtable 。 根据应用程序的复杂性,使用其他答案中已经提出的包装库可能是更好的手动处理解决方案。

为了完成答案(并且我首先忘记了这一点,感谢编辑功能!),最好的方式就是进入final变量,检查是否为null然后putput回到1 。 变量应该是final因为它是不可变的。 编译器可能不需要这个提示,但它更清晰。

final HashMap map = generateRandomHashMap();
final Object key = fetchSomeKey();
final Integer i = map.get(key);
if (i != null) {
    map.put(i + 1);
} else {
    // do something
}

如果你不想依靠自动装箱,你应该说像map.put(new Integer(1 + i.getValue())); 代替。


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

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

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


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

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)相比,开销不应该太大。


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


如果您使用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集合的提交者。


您可以在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 ,但代价是空间消耗较高。


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

最大的成本是不得不在你的方法中两次扫描地图。 在我的,你只需要做一次。 只需获取值(如果不存在,它将被初始化)并增加它。


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

你可以看看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> ,所以你不会产生装箱成本。


由于很多人在Groovy的答案中搜索Java主题,因此您可以在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}

Map<String, Integer> map = new HashMap<>();
String key = "a random key";
int count = map.getOrDefault(key, 0);
map.put(key, count + 1);

这就是你用简单的代码增加一个值的方法。

效益:

  • 不为可变int创建另一个类
  • 短代码
  • 容易明白
  • 没有空指针异常

另一种方法是使用合并方法,但这仅仅是增加一个值而已。

map.merge(key, 1, (a,b) -> a+b);

建议:在大多数情况下,您应该关心代码可读性而不是性能提升。





collections