Java高效计数器

怼烎@ 2021-11-05 15:50 280阅读 0赞

翻译人员: 铁锚  
翻译时间: 2013年11月3日  
原文链接: [Efficient Counter in Java][]  
  
我们经常使用 HashMap作为计数器(counter)来统计数据库或者文本中的某些东西.  
本文将使用HashMap来实现计数器的3种不同方式进行对比。  
  
**1. 新手级计数器**  
如果使用这一类别的计数器,那么代码大致如下所示:

1.  `String source = "my name is name me and your name is her first her";`
2.  `String[] words = source.split(" ");`
3.  `// 新手级计数器`
4.  `public static void testNaive(String[] words){`
5.  `HashMap<String, Integer> counter = new HashMap<String, Integer>();`
6.  `for (String w : words) {`
7.  `if(counter.containsKey(w)){`
8.  `int oldValue = counter.get(w);`
9.  `counter.put(w, oldValue+1);`
10. `} else {`
11. `counter.put(w, 1);`
12. `}`
13. `}`
14. `}`

在每次循环中,判断是否包含了相应的key,如果包含,那么值在原来的基础上加1,如果没有,那就设置为1.  
此种方式简单又直接,但并不是很有效率。效率不高的原因如下:  
1.1 当一个key存在时,containsKey() 和 get() 分别调用了一次,这意味着对map进行了两次查找。  
1.2 因为 Integer 是不可变的,每次循环在增加计数值的时候将会创建一个新的对象.  
  
  
**2. 入门级计数器**  
那么我们自然需要使用一个可变的整数来避免创建太多个Integer对象.可变整数类可以如下面所示来定义:

1.  `// 可变Integer`
2.  `public static final class MutableInteger{`
3.  `private int val;`
4.  `public MutableInteger(int val){`
5.  `this.val = val;`
6.  `}`
7.  `public int get(){`
8.  `return this.val;`
9.  `}`
10. `public void set(int val){`
11. `this.val = val;`
12. `}`
13. `// 为了方便打印`
14. `public String toString() {`
15. `return Integer.toString(val);`
16. `}`
17. `}`

那么计数器可以用如下的方式来改进:

1.  `// 入门级计数器`
2.  `public static void testBetter(String[] words){`
3.  `HashMap<String, MutableInteger> counter = new HashMap<String, MutableInteger>();`
4.  `for (String w : words) {`
5.  `if(counter.containsKey(w)){`
6.  `MutableInteger oldValue = counter.get(w);`
7.  `oldValue.set(oldValue.get()+1); // 因为是引用,所以减少了一次HashMap查找`
8.  `} else {`
9.  `counter.put(w, new MutableInteger(1));`
10. `}`
11. `}`
12. `}`

因为不需要创建太多的Integer对象,看起来好了一些。然而,key存在的情况下,每次循环依然要进行两次查找.  
  
3**. 卓越级计数器**  
HashMap 的 put(key,value) 方法会返回key对应的当前value.了解这个特性,我们可以利用原有值来进行递增,并不需要多次的查找.

1.  `public static void testEfficient(String[] words){`
2.  `HashMap<String, MutableInteger> counter = new HashMap<String, MutableInteger>();`
3.  `for (String w : words) {`
4.  `MutableInteger initValue = new MutableInteger(1);`
5.  `// 利用 HashMap 的put方法弹出旧值的特性`
6.  `MutableInteger oldValue = counter.put(w, initValue);`
7.  `if(oldValue != null){`
8.  `initValue.set(oldValue.get() + 1);`
9.  `}`
10. `}`
11. `}`

**4. 性能差异**  
为了测试这三种实现方式的性能,采用了下面的代码。先看看结果如何,性能测试分别执行了多次,对每一个数量级的测试,误差不算太大,所以取其中的一个结果排列如下:

1.  `10000000 次循环:`
2.  `新手级计数器: 7726594902`
3.  `入门级计数器: 6516014840`
4.  `卓越级计数器: 5736574103`
5.  
6.  
7.  `1000000 次循环:`
8.  `新手级计数器: 777480106`
9.  `入门级计数器: 642932000`
10. `卓越级计数器: 571867738`
11. 
12. 
13. `100000 次循环:`
14. `新手级计数器: 84323682`
15. `入门级计数器: 70176906`
16. `卓越级计数器: 61219664`
17. 
18. 
19. `10000 次循环:`
20. `新手级计数器: 13279550`
21. `入门级计数器: 7874100`
22. `卓越级计数器: 6460172`
23. 
24. 
25. `1000 次循环:`
26. `新手级计数器: 4542172`
27. `入门级计数器: 2933248`
28. `卓越级计数器: 992749`
29. 
30. 
31. `100 次循环:`
32. `新手级计数器: 3092325`
33. `入门级计数器: 1101695`
34. `卓越级计数器: 423942`
35. 
36. 
37. `10 次循环:`
38. `新手级计数器: 1993788`
39. `入门级计数器: 558150`
40. `卓越级计数器: 153156`
41. 
42. 
43. `1 次循环:`
44. `新手级计数器: 1625898`
45. `入门级计数器: 427494`
46. `卓越级计数器: 69473`

从上面的输出可以看到,10000次的时候, 13:8:6 秒,相差很明显.特别是 新手级计数器和入门级计数器之间的比例,这说明创建对象是很耗资源的操作。  
当然,次数更多的差距不明显的原因在于,触发了多次的GC垃圾回收,同时也证明了垃圾回收的代价确实很大。  
  
完整的测试代码如下:

1.  `import java.util.HashMap;`
2.  
3.  `public class TestCounter {`
4.  
5.  `public static void main(String[] args) {`
6.  `// 源字符串`
7.  `String source = "my name is name me and your name is her first her";`
8.  `// 计时,单位: 微秒`
9.  `long startTime = 0;`
10. `long endTime = 0;`
11. `long duration = 0;`
12. `// 测试次数`
13. `int loop = 1 * 10000;`
14. 
15. `System.out.println(loop +" 次循环:");`
16. `startTime = System.nanoTime();`
17. `testNaive(source,loop);`
18. `endTime = System.nanoTime();`
19. `duration = endTime - startTime;`
20. `System.out.println("新手级计数器: " + duration);`
21. `//`
22. `startTime = System.nanoTime();`
23. `testBetter(source, loop);`
24. `endTime = System.nanoTime();`
25. `duration = endTime - startTime;`
26. `System.out.println("入门级计数器: " + duration);`
27. `//`
28. `startTime = System.nanoTime();`
29. `testEfficient(source, loop);`
30. `endTime = System.nanoTime();`
31. `duration = endTime - startTime;`
32. `System.out.println("卓越级计数器: " + duration);`
33. `}`
34. 
35. `// 新手级计数器`
36. `public static void testNaive(String source, int loop){`
37. `if(null == source){`
38. `return;`
39. `}`
40. `//`
41. `String[] words = source.split(" ");`
42. `for (int i = 0; i < loop; i++) {`
43. `testNaive(words);`
44. `}`
45. `}`
46. `public static void testNaive(String[] words){`
47. `HashMap<String, Integer> counter = new HashMap<String, Integer>();`
48. `for (String w : words) {`
49. `if(counter.containsKey(w)){`
50. `int oldValue = counter.get(w);`
51. `counter.put(w, oldValue+1);`
52. `} else {`
53. `counter.put(w, 1);`
54. `}`
55. `}`
56. `}`
57. `// 可变Integer`
58. `public static final class MutableInteger{`
59. `private int val;`
60. `public MutableInteger(int val){`
61. `this.val = val;`
62. `}`
63. `public int get(){`
64. `return this.val;`
65. `}`
66. `public void set(int val){`
67. `this.val = val;`
68. `}`
69. `// 为了方便打印`
70. `public String toString() {`
71. `return Integer.toString(val);`
72. `}`
73. `}`
74. 
75. `// 入门级计数器`
76. `public static void testBetter(String source, int loop){`
77. `if(null == source){`
78. `return;`
79. `}`
80. `//`
81. `String[] words = source.split(" ");`
82. `for (int i = 0; i < loop; i++) {`
83. `testBetter(words);`
84. `}`
85. `}`
86. `public static void testBetter(String[] words){`
87. `HashMap<String, MutableInteger> counter = new HashMap<String, MutableInteger>();`
88. `for (String w : words) {`
89. `if(counter.containsKey(w)){`
90. `MutableInteger oldValue = counter.get(w);`
91. `oldValue.set(oldValue.get()+1); // 因为是引用,所以减少了一次HashMap查找`
92. `} else {`
93. `counter.put(w, new MutableInteger(1));`
94. `}`
95. `}`
96. `}`
97. 
98. `// 卓越级计数器`
99. `public static void testEfficient(String source, int loop){`
100. `if(null == source){`
101. `return;`
102. `}`
103. `//`
104. `String[] words = source.split(" ");`
105. `for (int i = 0; i < loop; i++) {`
106. `testEfficient(words);`
107. `}`
108. `}`
109. `public static void testEfficient(String[] words){`
110. `HashMap<String, MutableInteger> counter = new HashMap<String, MutableInteger>();`
111. `for (String w : words) {`
112. `// 利用 HashMap 的put方法弹出旧值的特性`
113. `MutableInteger oldValue = counter.get(w);`
114. `if(oldValue == null){`
115. `counter.put(k,new MutableInteger(0));`
116. `}`
117. `oldValue.add();`
118. `}`
119. `}`
120. `}`

当你实用计数器的时候,很可能也需要根据值来进行排序的方法,请参考: [the frequently used method of HashMap][].

**5. Keith网站评论列表**  
我觉得最好的评论如下:  
  
*添加了三个测试:  
1) 重构了 “入门级计数器”,不使用containsKey,改为只使用get方法. 通常你需要的元素是存在于 HashMap 中的, 所以将 2 次查找精简为 1次.  
2) 作者 michal 提到过的方式,使用 AtomicInteger来实现 .  
3) 使用单个的int 数组来进行对比,可以使用更少的内存,参见 http://amzn.com/0748614079  
  
  
我运行了测试程序3次,并挑选出最小的那个值(以减少干扰). 注意: 你不能在程序中让运行结果受到太多干扰,因为内存不足可能会受到gc垃圾回收器太多的影响.  
  
  
新手级计数器: 201716122  
入门级计数器: 112259166  
卓越级计数器: 93066471  
入门级计数器 (不使用 containsKey): 69578496  
入门级计数器 (不使用 containsKey, with AtomicInteger): 94313287  
入门级计数器 (不使用 containsKey, with int\[\]): 65877234  
  
入门级计数器 (不使用 containsKey 方法:):*

1.  `HashMap<string, mutableinteger=""> efficientCounter2 = new HashMap<string, mutableinteger="">();`
2.  `for (int i = 0; i < NUM_ITERATIONS; i++)`
3.  `for (String a : sArr) {`
4.  `MutableInteger value = efficientCounter2.get(a);`
5.  
6.  `if (value != null) {`
7.  `value.set(value.get() + 1);`
8.  `}`
9.  `else {`
10. `efficientCounter2.put(a, new MutableInteger(1));`
11. `}`
12. `}`

*入门级计数器 (不使用 containsKey, 使用 AtomicInteger):*

1.  `HashMap<string, atomicinteger=""> atomicCounter = new HashMap<string, atomicinteger="">();`
2.  `for (int i = 0; i < NUM_ITERATIONS; i++)`
3.  `for (String a : sArr) {`
4.  `AtomicInteger value = atomicCounter.get(a);`
5.  
6.  `if (value != null) {`
7.  `value.incrementAndGet();`
8.  `}`
9.  `else {`
10. `atomicCounter.put(a, new AtomicInteger(1));`
11. `}`
12. `}`

*入门级计数器 (不使用 containsKey, 使用 int\[\]):*

1.  `HashMap<string, int[]=""> intCounter = new HashMap<string, int[]="">();`
2.  `for (int i = 0; i < NUM_ITERATIONS; i++)`
3.  `for (String a : sArr) {`
4.  `int[] valueWrapper = intCounter.get(a);`
5.  
6.  `if (valueWrapper == null) {`
7.  `intCounter.put(a, new int[] { 1 });`
8.  `}`
9.  `else {`
10. `valueWrapper[0]++;`
11. `}`
12. `}`

***Guava 语言的 MultiSet 可能更快一些.***  
  
  
**6. 结论**  
优胜者是使用int数组的方式.  
  
  
**参考文章**

1. [Most efficient way to increment a Map value in Java][].

2. [HashMap.put()][HashMap.put] [HashMap.put()][HashMap.put 1]  
  
相关阅读  
1. [ArrayList vs. LinkedList vs. Vector][]

2. [HashSet vs. TreeSet vs. LinkedHashSet][]

3. [Frequently Used Methods of Java HashMap][the frequently used method of HashMap]

4. [Java Convert Hashtable to Treemap][]

[Efficient Counter in Java]: http://www.programcreek.com/2013/10/efficient-counter-in-java/
[the frequently used method of HashMap]: http://www.programcreek.com/2013/04/frequently-used-methods-of-java-hashmap/
[Most efficient way to increment a Map value in Java]: http://blog.pengyifan.com/most-efficient-way-to-increment-a-map-value-in-java-only-search-the-key-once/
[HashMap.put]: http://docs.oracle.com/javase/6/docs/api/java/util/HashMap.html#put%28K,
[HashMap.put 1]: https://blog.csdn.net/renfufei/article/details/V%29
[ArrayList vs. LinkedList vs. Vector]: http://www.programcreek.com/2013/03/arraylist-vs-linkedlist-vs-vector/
[HashSet vs. TreeSet vs. LinkedHashSet]: http://www.programcreek.com/2013/03/hashset-vs-treeset-vs-linkedhashset/
[Java Convert Hashtable to Treemap]: http://www.programcreek.com/2009/01/code-example-with-java-hashtable/