• 欢迎访问天天编码网站,Java技术、技术书单、开发工具,欢迎加入天天编码
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏天天编码吧
  • 我们的淘宝店铺已经开张了哦,传送门:https://shop145764801.taobao.com/

Java中最高效的统计方式

Java基础 tiantian 2207次浏览 5个评论 扫描二维码

在实际的编程项目中,经常需要一个计数器来统计某些事情(单词)的出现频率。比如,一个文本文件或者一张数据库的表中特定的单词出现了多少此?在Java中,如何实现一个这样的计数器呢?最简单的方式可能是利用JDK中的HashMap集合。当然了,实现计数器的方式有很多种,那么哪一种才是最高效的呢?本文将介绍和分析各种实现计数器的方式,并选取出最高效的那种。

Java中最高效的统计方式

简单方式

直接利用HashMap集合的特性,示例代码如下:

String strA = "www. tian tian bian ma .com 天 天 编 码";
String[] strArr = strA.split(" ");

HashMap<String, Integer> counter = new HashMap<String, Integer>();
for (String str : strArr) {
if (counter.containsKey(str)) {
int oldValue = counter.get(str);
counter.put(strA, oldValue + 1);
} else {
counter.put(strA, 1);
}
}

可以看到,该示例的逻辑非常简单。在每一次循环时,检查HashMap中是否已经存在该单词:如果存在,就在原来的基础上加1;如果不存在,就把该单词对应的频率设为1。该方法虽然逻辑简单,直接,但确实一个不高效的方法。如果再考虑如下两个因素,该方法的效率就更低了。
1. 当一个key存在时,containsKey(),get()方法被调用了两次,这需要搜索HashMap两次。
2. 因为 Integer 本身就不可变的,每次的循环都有创建一个新的 Integer 值。

改进方法

很自然地,我们可以通过避免每次循环时的创建新 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;
}

@Override
public String toString() {
return Integer.toString(val);
}
}

这样以后,我们可以使用该可变的 MutableInteger 来提高计数器的性能:

HashMap<String, MutableInteger> newCounter = new HashMap<String, MutableInteger>();

for (String str : strArr) {
if (newCounter.containsKey(str)) {
MutableInteger oldValue = newCounter.get(str);
oldValue.set(oldValue.get() + 1);
} else {
newCounter.put(str, new MutableInteger(1));
}
}

经过这样的改造后,循环过程中不再需要创建大量 Integer 对象,提高了程序的性能。不过,当一个key存在是,每次循环还是需要两次搜索集合HashMap。

高效方法

细心的读者可能注意到了:HashMap.put(key, value) 方法会返回这个key的当前值。这是一个很有用处的特性,因为,我们可以利用返回的旧值的引用直接来更新其值,而不需要再搜寻一遍HashMap集合。

HashMap<String, MutableInteger> efficientCounter = new HashMap<String, MutableInteger>();

for (String str : strArr) {
MutableInteger initValue = new MutableInteger(1);
MutableInteger oldValue = efficientCounter.put(str, initValue);

if (oldValue != null) {
initValue.set(oldValue.get() + 1);
}
}

性能测量

目前为止,本文已经提供了三种实现计数器的方法,那么它们的性能表现如何呢?是否正如我们所推测的那样,性能越来越高呢?我们利用如下所示的代码片段来实际测量一下:

String strA = "www. tian tian bian ma .com 天 天 编 码";
String[] strArr = strA.split(" ");

long startTime = 0;
long endTime = 0;
long duration = 0;

startTime = System.nanoTime();
HashMap<String, Integer> counter = new HashMap<String, Integer>();

for (int i = 0; i < 1000000; i++) {
// 各个计数器的核心代码

}
endTime = System.nanoTime();
duration = endTime - startTime;
System.out.println("duration : " + duration);

通过使用该方式,测量得出的结果如下:

简单方法:222796000
改进方法:117283000
高效方法:96374000

我们可以看到,在改进方法、高效方法与简单方法之前,存在这巨大的性能差异,这意味着创建新对象的成本是巨大的。

在你使用计数器的过程中,如果需要根据value值来排序HashMap,建议查看本站的这篇文章

更多思路

实际上,本文前面给出的三个方法都还有不少的改进空间。我们来看看其中的三种改进方案。
1. 重构“改进方法”,使用 get 方法代替 containsKey 方法,通常来说,计数的目标元素存在的可能性很大,从而使得两次搜寻减少成一次。
2. 使用 AtomicInteger。
3. 使用单例的 int 数组,使用更少的内存空间。

这三种改进思路的示例代码如下:
改进方法(不使用 containsKey)

HashMap<String, MutableInteger> efficientCounter = new HashMap<>();
for (int i = 0; i < 100000; i++) {
for (String str : strArr) {
MutableInteger value = efficientCounter.get(str);
if (value != null) {
value.set(value.get() + 1);
} else {
efficientCounter.put(str, new MutableInteger(1));
}
}
}

改进方法(不使用 containsKey, 使用AtomicInteger)

HashMap<String, AtomicInteger> efficientCounter = new HashMap<>();
for (int i = 0; i < 100000; i++) {
for (String str : strArr) {
AtomicInteger value = efficientCounter.get(str);
if (value != null) {
value.incrementAndGet();
} else {
efficientCounter.put(str, new AtomicInteger(1));
}
}
}

改进方法(不使用 containsKey, 使用 int[])

HashMap<String, int[]> efficientCounter = new HashMap<>();
for (int i = 0; i < 100000; i++) {
for (String str : strArr) {
int[] value = efficientCounter.get(str);
if (value != null) {
value.[0]++;
} else {
efficientCounter.put(str, new int[] {1});
}
}
}

最后,我们使用同样的测量代码,得出的测量结果是:

简单方法: 201716122
改进方法:  112259166
高效方法: 93066471
改进方法(不使用 containsKey):69578496
改进方法(不使用 containsKey,使用 AtomicInteger):94313287
改进方法(不使用 containsKey, 使用 int[]):65877234

总结

为了获取性能最好的计数器,本文从最简单、最直接的思路出发,一步步优化代码,最终获得了六个实现计数器的方法。最后,使用一个示例代码对六种方法进行测量,也许测量方法不够精确,但最终结果是可信的,最好的方法是 不使用 containsKey方法,使用 int[]的方法。


天天编码 , 版权所有丨本文标题:Java中最高效的统计方式
转载请保留页面地址:http://www.tiantianbianma.com/java-effiective-count.html/
喜欢 (8)
支付宝[多谢打赏]
分享 (0)
发表我的评论
取消评论

表情 贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
(5)个小伙伴在吐槽
  1. 简单方式中 counter.put(strA, oldValue + 1);和counter.put(strA, 1); strA应该改成 str
    匿名2017-10-29 10:26 回复 Windows 7 | Chrome 60.0.3112.101
    • :smile:
      tiantian2017-11-02 16:21 回复 Windows 10 | Chrome 61.0.3163.100
  2. int[]为什么比int要好,不也是int[0]吗
    摩羯小乐2017-11-27 15:09 回复 Windows 10 | 搜狗浏览器 2.X
  3. 实测了下,结果不太一样呢
    xiari2018-01-26 14:15 回复 Windows 8.1 | Firefox 55.0
    • 在什么版本的JDK做的测试呢?提供一下具体的测试结果?
      tiantian2018-03-17 16:59 回复 Windows 7 | Chrome 64.0.3282.186