现在的位置: 首页 > 综合 > 正文

Java高效计数器

2014年02月16日 ⁄ 综合 ⁄ 共 2871字 ⁄ 字号 小 中 大 ⁄ 评论关闭

翻译人员: 铁锚
翻译时间: 2013年11月3日
原文链接: Efficient
Counter in Java

我们经常使用 HashMap作为计数器(counter)来统计数据库或者文本中的某些东西.
本文将使用HashMap来实现计数器的3种不同方式进行对比。

1. 新手级计数器
如果使用这一类别的计数器,那么代码大致如下所示:

[java] view
plaincopy

  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对象.可变整数类可以如下面所示来定义:

[java] view
plaincopy

  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. }  


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

[java] view
plaincopy

  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.了解这个特性,我们可以利用原有值来进行递增,并不需要多次的查找.

[java] view
plaincopy

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

[plain] view
plaincopy

  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  
返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

Copyright © 2013-2018 学步园  保留所有权利.
软文销售 QQ客服：2265327166 点击这里给我发消息（其他合作也可洽谈）
必威体育
必威电竞