Java高效计数器 怼烎@ 2021-11-05 15:50 274阅读 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/
还没有评论,来说两句吧...