Translate from Efficient Counter in Java
Java中的高效计数器
你可能经常需要统计一段文本或数据库中某些东西（例如单词）的出现频率。在Java中，使用HashMap可以很简单的实现这么一个计数器。
这篇文章将会比较几种实现计数器的方法，最后，得出最有效率的一个。
1. 简单计数器
String s = "one two three two three three";
String[] sArr = s.split(" ");
//naive approach
HashMap<String, Integer> counter = new HashMap<String, Integer>();
for (String a : sArr) {
if (counter.containsKey(a)) {
int oldValue = counter.get(a);
counter.put(a, oldValue + 1);
} else {
counter.put(a, 1);
}
}
每次循环，检查map中是否已经有该字符，如果有则value+1；如果没有，则放入map,把value置为1；
这种方法很简单，但是效率不够，体现在以下两点：
- 当key值已经存在时，调用了两次方法：containsKey()、get()，这意味着要在map中检索两次
- 由于Integer是不可变的，每个循环增加key的value时会创建一个新的对象
2. 优化计数器
为了避免Integer的“不可变”带来的重新创建对象的问题，我们创建一个“可变”的Integer对象：
class MutableInteger {
private int val;
public MutableInteger(int val) {
this.val = val;
}
public int get() {
return val;
}
public void set(int val) {
this.val = val;
}
//used to print value convinently
public String toString(){
return Integer.toString(val);
}
}
通过这个可变的Integer对象，改进后的计数器代码如下：
HashMap<String, MutableInteger> newCounter = new HashMap<String, MutableInteger>();
for (String a : sArr) {
if (newCounter.containsKey(a)) {
MutableInteger oldValue = newCounter.get(a);
oldValue.set(oldValue.get() + 1);
} else {
newCounter.put(a, new MutableInteger(1));
}
}
优化了两个地方：
- 每次value+1时不需要重新创建Integer对象了
- 改变value值不需要重新put()进去
但是，这个方法仍然进行了两次检索
3. 高效计数器
由于 HashMap.put(key, value)方法会返回这个key值原有的value，我们可以利用这一点避免两次检索
（译者注：但是每次循环又增加了一个对象创建的开销）
HashMap<String, MutableInteger> efficientCounter = new HashMap<String, MutableInteger>();
for (String a : sArr) {
MutableInteger initValue = new MutableInteger(1);
MutableInteger oldValue = efficientCounter.put(a, initValue);
if(oldValue != null){
initValue.set(oldValue.get() + 1);
}
}
4. 三种方法的效率表现
为了体现三种方法的效率，通过代码循环了一百万次进行测试，结果如下：
Naive Approach : 222796000
Better Approach: 117283000
Efficient Approach: 96374000
结果可以近似表达为：223:117:96，简单计数器和优良计数器之间的差距很大，这证明了创建对象的时间花费很大！
String s = "one two three two three three";
String[] sArr = s.split(" ");
long startTime = 0;
long endTime = 0;
long duration = 0;
// naive approach
startTime = System.nanoTime();
HashMap<String, Integer> counter = new HashMap<String, Integer>();
for (int i = 0; i < 1000000; i++)
for (String a : sArr) {
if (counter.containsKey(a)) {
int oldValue = counter.get(a);
counter.put(a, oldValue + 1);
} else {
counter.put(a, 1);
}
}
endTime = System.nanoTime();
duration = endTime - startTime;
System.out.println("Naive Approach : " + duration);
// better approach
startTime = System.nanoTime();
HashMap<String, MutableInteger> newCounter = new HashMap<String, MutableInteger>();
for (int i = 0; i < 1000000; i++)
for (String a : sArr) {
if (newCounter.containsKey(a)) {
MutableInteger oldValue = newCounter.get(a);
oldValue.set(oldValue.get() + 1);
} else {
newCounter.put(a, new MutableInteger(1));
}
}
endTime = System.nanoTime();
duration = endTime - startTime;
System.out.println("Better Approach: " + duration);
// efficient approach
startTime = System.nanoTime();
HashMap<String, MutableInteger> efficientCounter = new HashMap<String, MutableInteger>();
for (int i = 0; i < 1000000; i++)
for (String a : sArr) {
MutableInteger initValue = new MutableInteger(1);
MutableInteger oldValue = efficientCounter.put(a, initValue);
if (oldValue != null) {
initValue.set(oldValue.get() + 1);
}
}
endTime = System.nanoTime();
duration = endTime - startTime;
System.out.println("Efficient Approach: " + duration);
5. Keith网站上的更好方法
增加了三个测试：
- 重构优良计数器，用get方法取代了containKey，这样HashMap里面的两次检索减成了一个
- 取消自定义可变类型的Integer类，用Java中的AtomicInteger
- 根据How to Do Text Analysis with Java 一书，value改为用单个int数组存储，可使用更少内存。
我运行这个改进测试案例三次，取结果中最小的值来避免其他程序的影响。注意，你不能让你的程序受到太多影响干扰。例如内存不足会让垃圾回收机制器进行回收。
Naive: 201716122
Better Approach: 112259166
Efficient Approach: 93066471
Better Approach (without containsKey): 69578496
Better Approach (without containsKey, with AtomicInteger): 94313287
Better Approach (without containsKey, with int[]): 65877234
以下是代码
更好的方法（取消使用containsKey）:
HashMap<String, MutableInteger> efficientCounter2 = new HashMap<String, MutableInteger>();
for (int i = 0; i < NUM_ITERATIONS; i++) {
for (String a : sArr) {
MutableInteger value = efficientCounter2.get(a);
if (value != null) {
value.set(value.get() + 1);
} else {
efficientCounter2.put(a, new MutableInteger(1));
}
}
}
更好的方法（取消使用containsKey，用AtomicInteger）:
HashMap<String, AtomicInteger> atomicCounter = new HashMap<String, AtomicInteger>();
for (int i = 0; i < NUM_ITERATIONS; i++) {
for (String a : sArr) {
AtomicInteger value = atomicCounter.get(a);
if (value != null) {
value.incrementAndGet();
} else {
atomicCounter.put(a, new AtomicInteger(1));
}
}
}
更好的方法（取消使用containsKey，用int[]）:
HashMap<String, int[]> intCounter = new HashMap<String, int[]>();
for (int i = 0; i < NUM_ITERATIONS; i++) {
for (String a : sArr) {
int[] valueWrapper = intCounter.get(a);
if (valueWrapper == null) {
intCounter.put(a, new int[] { 1 });
} else {
valueWrapper[0]++;
}
}
}
6. 结论
efficient-counter.png
从图可以看出，最终胜利者是最后一个使用int[]数组的方法
参考：
1.Most efficient way to increment a Map value in Java.
2.[HashMap.put()](http://docs.oracle.com/javase/6/docs/api/java/util/HashMap.html#put(K, V))
7. 译者补充
这里进一步对高效计数器和改进版的高效计数器进行一下对比
测试字符串"one two three two three three"，都采用int[]数组存储
- 原本高效计数器：去除了两次检索，但每次循环都声明了一个新对象
for (String string : sArray) {
int[] n=new int[]{1};
int[] num = map.put(string,n);
if (num != null)
n[0]=++num[0];
}
- 网站改进版：需要一次检索，但没有声明多余的对象
for (String key: sArray) {
int[] n=map.get(key);
if(n==null)
map.put(key, new int[]{1});
else
n[0]++;
}
三次运行得出最终耗时结果
48396425
26244898
在这个例子我们似乎可以看出，依旧是改进版的计数器更高效。
但如果把字符串延长10倍，再次运行
21581658187
22019343923
此时两种方法时间花费特别接近，如果把字符串继续延长，改进版的效率则不一定比原来的高。
所以这里得出我的结论：
没有最高效的计数器，只有最合适的计数器。在字符串比较小的情况下，本文末尾结论的计数器最高效。但字符串增加， HashMap检索代价增加的情况下，则第一种高效计数器更好。
网友评论