我希望这个问题对于这个论坛来说不算太基础，但我们会看到。 我想知道如何重构一些代码以获得更好的性能，这些代码会运行很多次。
假设我正在使用Map(可能是HashMap)创建一个单词频率列表，其中每个键都是一个字符串，其中包含要计数的单词，而值是一个整数，每次找到该单词的标记时，该整数都会递增。
在Perl中，增加这样的值将非常简单：
但在Java中，它要复杂得多。 这是我目前正在做的方式：
1
2
| int count = map.containsKey(word) ? map.get(word) : 0;
map.put(word, count + 1); |
这当然依赖于较新Java版本中的自动装箱功能。 我想知道你是否可以提出一种更有效的方法来增加这样的价值。 是否有良好的性能原因可以避开Collections框架并使用其他东西？
更新：我已经对几个答案进行了测试。 见下文。
一些测试结果
我已经得到了很多这个问题的好答案 - 感谢大家 - 所以我决定运行一些测试并找出哪种方法实际上最快。我测试的五种方法是：
-
我在问题中提出的"ContainsKey"方法
-
Aleksandar Dimitrov建议的"TestForNull"方法
-
Hank Gay建议的"AtomicLong"方法
-
jrudolph建议的"Trove"方法
-
phax.myopenid.com建议的"MutableInt"方法
方法
这就是我做的......
创建了五个相同的类，除了下面显示的差异。每个类都必须执行我所呈现的场景的典型操作：打开10MB文件并读入，然后执行文件中所有单词令牌的频率计数。由于这平均只花了3秒钟，我让它执行频率计数(不是I / O)10次。
定时循环10次迭代而不是I / O操作，并记录了基本上使用Java Cookbook中的Ian Darwin方法所花费的总时间(以秒为单位)。
连续完成了所有五项测试，然后又做了三次。
平均每种方法的四个结果。
结果
我将首先介绍结果，并为感兴趣的人提供下面的代码。
正如预期的那样，ContainsKey方法是最慢的，所以我将给出每种方法的速度与该方法的速度相比较。
-
ContainsKey：30.654秒(基线)
-
AtomicLong：29.780秒(快1.03倍)
-
TestForNull：28.804秒(快1.06倍)
-
Trove：26.313秒(快了1.16倍)
-
MutableInt：25.747秒(快了1.19倍)
结论
似乎只有MutableInt方法和Trove方法明显更快，因为只有它们的性能提升超过10％。但是，如果线程是一个问题，AtomicLong可能比其他人更有吸引力(我不太确定)。我还用final变量运行TestForNull，但差别可以忽略不计。
请注意，我没有在不同的场景中分析内存使用情况。我很高兴听到任何人对MutableInt和Trove方法如何影响内存使用情况有很好的见解。
就个人而言，我发现MutableInt方法最具吸引力，因为它不需要加载任何第三方类。因此，除非我发现它的问题，这是我最有可能的方式。
代码
以下是每种方法的关键代码。
的containsKey
1
2
3
4
5
6
7
| 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
1
2
3
4
5
6
7
8
9
10
11
12
| 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
1
2
3
4
5
6
7
8
9
| 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(); |
特罗韦
1
2
3
4
5
| import gnu.trove.TObjectIntHashMap;
...
TObjectIntHashMap<String> freq = new TObjectIntHashMap<String>();
...
freq.adjustOrPutValue(word, 1, 1); |
MutableInt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| 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();
} |
好的，可能是一个老问题，但Java 8有一个更短的方法：
1
| Map.merge(key, 1, Integer::sum) |
它的作用：如果key不存在，则将1作为值，否则将1加到与key相关的值。
更多信息在这里
2016年的一点研究：https：//github.com/leventov/java-word-count，基准源代码
每种方法的最佳结果(越小越好)：
1
2
3
4
5
6
7
8
9
10
11
| time, ms
kolobokeCompile 18.8
koloboke 19.8
trove 20.8
fastutil 22.7
mutableInt 24.3
atomicInteger 25.3
eclipse 26.9
hashMap 28.0
hppc 33.6
hppcRt 36.5 |
时间空间结果：
谷歌番石榴是你的朋友......
......至少在某些情况下。他们有这个漂亮的AtomicLongMap。特别好，因为你在地图上处理的价值很长。
例如。
1
2
3
| AtomicLongMap<String> map = AtomicLongMap.create();
[...]
map.getAndIncrement(word); |
也可以为值添加多于1：
1
| map.getAndAdd(word, 112L); |
@Hank Gay
作为我自己(相当无用的)评论的后续行动：Trove看起来像是要走的路。无论出于何种原因，如果你想坚持使用标准的JDK，ConcurrentMap和AtomicLong可以让代码变得更好，尽管是YMMV。
1
2
3
| final ConcurrentMap<String, AtomicLong> map = new ConcurrentHashMap<String, AtomicLong>();
map.putIfAbsent("foo", new AtomicLong(0));
map.get("foo").incrementAndGet(); |
将1作为foo地图中的值。实际上，增加对线程的友好性就是这种方法必须推荐的。
查看Google Collections Library以获取此类内容始终是个好主意。在这种情况下，Multiset可以解决这个问题：
1
2
3
4
5
| Multiset bag = Multisets.newHashMultiset();
String word ="foo";
bag.add(word);
bag.add(word);
System.out.println(bag.count(word)); // Prints 2 |
有类似于Map的方法来迭代键/条目等。在内部，实现当前使用HashMap，因此您不会产生拳击成本。
你应该知道你原来的尝试
1
| int count = map.containsKey(word) ? map.get(word) : 0; |
在地图上包含两个可能很昂贵的操作，即containsKey和get。前者执行的操作可能与后者非常相似，所以你要做两次同样的工作！
如果查看Map的API，当映射不包含请求的元素时，get操作通常会返回null。
请注意，这将成为一个解决方案
1
| map.put( key, map.get(key) + 1 ); |
危险，因为它可能会产生NullPointerException s。您应该首先检查null。
另请注意，这非常重要，HashMap可以包含nulls的定义。所以不是每个返回的null都说"没有这样的元素"。在这方面，containsKey在实际上告诉您是否存在这样的元素时与get的行为不同。有关详细信息，请参阅API。
但是，对于您的情况，您可能不想区分存储的null和"noSuchElement"。如果您不想允许null s，您可能更喜欢Hashtable。使用其他答案中已经提出的包装库可能是手动处理的更好解决方案，具体取决于应用程序的复杂程度。
为了完成答案(我忘了先把它放进去，多亏了编辑功能！)，本地做的最好方法是将get变成final变量，检查null和< x20>用1返回。变量应该是final因为它无论如何都是不可变的。编译器可能不需要这个提示，但它更清晰。
1
2
3
4
5
6
7
8
| 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()));之类的东西。
1
2
3
4
| Map<String, Integer> map = new HashMap<>();
String key ="a random key";
int count = map.getOrDefault(key, 0);
map.put(key, count + 1); |
这就是你用简单的代码增加一个值的方法。
效益：
-
不为mutable int创建另一个类
-
短代码
-
容易明白
-
没有空指针异常
另一种方法是使用合并方法，但这对于增加值来说太多了。
1
| map.merge(key, 1, (a,b) -> a+b); |
建议：在大多数情况下，您应该关注代码可读性而不是小的性能提升。
另一种方法是创建一个可变整数：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| 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)相比，开销不应该那么多。
您可以在Java 8中提供的Map接口中使用computeIfAbsent方法。
1
2
3
4
| 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，则返回null。
另外，如果您遇到多个线程更新公共总和的情况，您可以查看LongAdder类。在高争用情况下，此类的预期吞吐量明显高于AtomicLong，但代价是空间消耗较高。
内存轮换可能是一个问题，因为每次装入大于或等于128的int会导致对象分配(请参阅Integer.valueOf(int))。虽然垃圾收集器非常有效地处理短期对象，但性能会受到一定程度的影响。
如果您知道所做的增量数量将大大超过键的数量(在这种情况下为单词)，请考虑使用int holder。 Phax已经为此提供了代码。这里再次进行两次更改(holder类为static，初始值为1)：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| 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。
顺便说一下，这个主题的一个好的搜索词是"直方图"。
而不是调用containsKey()，只需调用map.get并检查返回的值是否为null。
1
2
3
4
5
| Integer count = map.get(word);
if(count == null){
count = 0;
}
map.put(word, count + 1); |
有几种方法：
使用像Google集合中包含的集合一样的Bag算法。
创建可在Map中使用的可变容器：
1
2
3
4
5
6
| <wyn>
class My{
String word;
int count;
}
</wyn> |
并使用put("word"，new My("Word"));然后你可以检查它是否存在并在添加时增加。
避免使用列表滚动您自己的解决方案，因为如果您进行内部搜索和排序，您的性能将会很糟糕。第一个HashMap解决方案实际上非常快，但像Google Collections中的那个更合适可能更好。
使用Google Collections计算单词，看起来像这样：
1
2
3
4
5
6
7
8
| <wyn>
HashMultiset s = new HashMultiset();
s.add("word");
s.add("word");
System.out.println(""+s.count("word") );
</wyn> |
使用HashMultiset是非常好的，因为在计算单词时你需要一个包算法。
MutableInt方法的一个变体可能更快，如果有点破解，是使用单元素int数组：
1
2
3
4
5
6
7
| 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的集合来减少我正在创建的一些非常大的地图中的内存大小 - 作为奖励，它也更快。
一个非常好的功能是TObjectIntHashMap类有一个adjustOrPutValue调用，根据该键是否已存在值，将放置初始值或增加现有值。这非常适合递增：
1
2
3
| TObjectIntHashMap<String> map = new TObjectIntHashMap<String>();
...
map.adjustOrPutValue(key, 1, 1); |
Google Collections HashMultiset：
- 使用起来相当优雅
- 但消耗CPU和内存
最好的方法是：Entry getOrPut(K);
(优雅，低成本)
这样的方法只计算一次哈希和索引，
然后我们可以用条目做我们想要的
(替换或更新值)。
更优雅：
- 拿一个HashSet
- 扩展它，以便get(K)在需要时放入一个新条目
- 条目可能是您自己的对象。
- > (new MyHashSet()).get(k).increment();
你确定这是一个瓶颈吗？你做过任何性能分析吗？
尝试使用NetBeans探查器(它是免费的并内置于NB 6.1中)来查看热点。
最后，JVM升级(比如从1.5-> 1.6)通常是一个廉价的性能助推器。即使是内部版本号的升级也可以提供良好的性能提升。如果您在Windows上运行并且这是服务器类应用程序，请在命令行上使用-server来使用Server Hotspot JVM。在Linux和Solaris计算机上，这是自动检测的。
我认为您的解决方案将是标准方式，但是 - 正如您自己指出的那样 - 它可能不是最快的方式。
你可以看看GNU Trove。这是一个包含各种快速原始集合的库。你的例子将使用一个TObjectIntHashMap，它有一个方法adjustOrPutValue，它完全符合你的要求。
"put"需要"get"(以确保没有重复键)。
所以直接做"放"，
如果有以前的值，那么做一个补充：
1
2
3
4
5
6
7
| Map map = new HashMap ();
MutableInt newValue = new MutableInt (1); // default = inc
MutableInt oldValue = map.put (key, newValue);
if (oldValue != null) {
newValue.add(oldValue); // old + inc
} |
如果count从0开始，则添加1 :(或任何其他值...)
1
2
3
4
5
6
7
| Map map = new HashMap ();
MutableInt newValue = new MutableInt (0); // default
MutableInt oldValue = map.put (key, newValue);
if (oldValue != null) {
newValue.setValue(oldValue + 1); // old + inc
} |
注意：此代码不是线程安全的。使用它来构建然后使用地图，而不是同时更新它。
优化：在循环中，保持旧值成为下一循环的新值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| Map map = new HashMap ();
final int defaut = 0;
final int inc = 1;
MutableInt oldValue = new MutableInt (default);
while(true) {
MutableInt newValue = oldValue;
oldValue = map.put (key, newValue); // insert or...
if (oldValue != null) {
newValue.setValue(oldValue + inc); // ...update
oldValue.setValue(default); // reuse
} else
oldValue = new MutableInt (default); // renew
}
} |
非常简单，只需使用Map.java中的内置函数即可
1
| map.put(key, map.getOrDefault(key, 0) + 1); |
@Vilmantas Baranauskas：关于这个答案，我会评论我是否有代表点，但我没有。我想要注意，那里定义的Counter类没有线程安全，因为仅仅同步inc()而不同步value()是不够的。除非已经与更新建立了先发生关系，否则不保证调用value()的其他线程看到该值。
我将使用Apache Collections Lazy Map(将值初始化为0)并使用Apache Lang中的MutableIntegers作为该映射中的值。
最大的成本是必须在方法中两次搜索地图。在我的，你只需要做一次。只需获取值(如果不存在则会初始化)并递增它。
如果您正在使用Eclipse集合，则可以使用HashBag。就内存使用而言，它将是最有效的方法，并且在执行速度方面也表现良好。
HashBag由MutableObjectIntMap支持，该MutableObjectIntMap存储原始int而不是Counter对象。这减少了内存开销并提高了执行速度。
HashBag提供了您需要的API，因为它是Collection，它还允许您查询项目的出现次数。
这是Eclipse Collections Kata的一个例子。
1
2
3
4
5
6
7
8
9
10
| 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 Collections的提交者。
我不知道它的效率如何，但下面的代码也可以。你需要在开头定义一个BiFunction。此外，您可以使用此方法进行更多增量。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| 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"));
} |
输出是
各种原始包装器，例如Integer是不可变的，所以除非你能用像AtomicLong这样的东西做，否则你真的没有更简洁的方法来做你想要的。我可以在一分钟内完成并更新。顺便说一下，Hashtable是Collections Framework的一部分。
Functional Java库的TreeMap数据结构在最新的主干头中有一个update方法：
1
| public TreeMap<K, V> update(final K k, final F<V, V> f) |
用法示例：
1
2
3
4
5
6
7
8
9
10
11
| 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"。
java 8中简单易用的方法如下：
1
2
| final ConcurrentMap<String, AtomicLong> map = new ConcurrentHashMap<String, AtomicLong>();
map.computeIfAbsent("foo", key -> new AtomicLong(0)).incrementAndGet(); |
由于很多人都在搜索Groovy答案的Java主题，所以这里是如何在Groovy中完成的：
1
2
3
4
5
| 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} |
希望我正确理解你的问题，我是从Python学习Java的，所以我可以同情你的斗争。
如果你有
你会的
1
| map.put(key, map.get(key) + 1) |
希望这可以帮助！
