翻译人员: 铁锚

翻译时间: 2013年11月3日

原文链接: Efficient Counter in Java

我们经常使用 HashMap作为计数器(counter)来统计数据库或者文本中的某些东西.

本文将使用HashMap来实现计数器的3种不同方式进行对比。

1. 新手级计数器

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

String source = "my name is name me and your name is her first her";

String[] words = source.split(" ");

// 新手级计数器

public static void testNaive(String[] words){

HashMap counter = new HashMap();

for (String w : words) {

if(counter.containsKey(w)){

int oldValue = counter.get(w);

counter.put(w, oldValue+1);

} else {

counter.put(w, 1);

}

}

}

在每次循环中,判断是否包含了相应的key,如果包含,那么值在原来的基础上加1,如果没有,那就设置为1.

此种方式简单又直接,但并不是很有效率。效率不高的原因如下:

1.1 当一个key存在时,containsKey() 和 get() 分别调用了一次,这意味着对map进行了两次查找。

1.2 因为 Integer 是不可变的,每次循环在增加计数值的时候将会创建一个新的对象.

2. 入门级计数器

那么我们自然需要使用一个可变的整数来避免创建太多个Integer对象.可变整数类可以如下面所示来定义:

// 可变Integer

public static final class MutableInteger{

private int val;

public MutableInteger(int val){

this.val = val;

}

public int get(){

return this.val;

}

public void set(int val){

this.val = val;

}

// 为了方便打印

public String toString() {

return Integer.toString(val);

}

}

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

// 入门级计数器

public static void testBetter(String[] words){

HashMap counter = new HashMap();

for (String w : words) {

if(counter.containsKey(w)){

MutableInteger oldValue = counter.get(w);

oldValue.set(oldValue.get()+1);// 因为是引用,所以减少了一次HashMap查找

} else {

counter.put(w, new MutableInteger(1));

}

}

}

因为不需要创建太多的Integer对象,看起来好了一些。然而,key存在的情况下,每次循环依然要进行两次查找.

3. 卓越级计数器

HashMap 的 put(key,value) 方法会返回key对应的当前value.了解这个特性,我们可以利用原有值来进行递增,并不需要多次的查找.

public static void testEfficient(String[] words){

HashMap counter = new HashMap();

for (String w : words) {

MutableInteger initValue = new MutableInteger(1);

// 利用 HashMap 的put方法弹出旧值的特性

MutableInteger oldValue = counter.put(w, initValue);

if(oldValue != null){

initValue.set(oldValue.get() + 1);

}

}

}

4. 性能差异

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

10000000 次循环:

新手级计数器: 7726594902

入门级计数器: 6516014840

卓越级计数器: 5736574103

1000000 次循环:

新手级计数器: 777480106

入门级计数器: 642932000

卓越级计数器: 571867738

100000 次循环:

新手级计数器: 84323682

入门级计数器: 70176906

卓越级计数器: 61219664

10000 次循环:

新手级计数器: 13279550

入门级计数器: 7874100

卓越级计数器: 6460172

1000 次循环:

新手级计数器: 4542172

入门级计数器: 2933248

卓越级计数器: 992749

100 次循环:

新手级计数器: 3092325

入门级计数器: 1101695

卓越级计数器: 423942

10 次循环:

新手级计数器: 1993788

入门级计数器: 558150

卓越级计数器: 153156

1 次循环:

新手级计数器: 1625898

入门级计数器: 427494

卓越级计数器: 69473

从上面的输出可以看到,10000次的时候, 13:8:6 秒,相差很明显.特别是 新手级计数器和入门级计数器之间的比例,这说明创建对象是很耗资源的操作。

当然,次数更多的差距不明显的原因在于,触发了多次的GC垃圾回收,同时也证明了垃圾回收的代价确实很大。

完整的测试代码如下:

import java.util.HashMap;

public class TestCounter {

public static void main(String[] args) {

// 源字符串

String source = "my name is name me and your name is her first her";

// 计时,单位: 微秒

long startTime = 0;

long endTime = 0;

long duration = 0;

// 测试次数

int loop = 1 * 10000;

System.out.println(loop +" 次循环:");

startTime = System.nanoTime();

testNaive(source,loop);

endTime = System.nanoTime();

duration = endTime - startTime;

System.out.println("新手级计数器: " + duration);

//

startTime = System.nanoTime();

testBetter(source, loop);

endTime = System.nanoTime();

duration = endTime - startTime;

System.out.println("入门级计数器: " + duration);

//

startTime = System.nanoTime();

testEfficient(source, loop);

endTime = System.nanoTime();

duration = endTime - startTime;

System.out.println("卓越级计数器: " + duration);

}

// 新手级计数器

public static void testNaive(String source, int loop){

if(null == source){

return;

}

//

String[] words = source.split(" ");

for (int i = 0; i < loop; i++) {

testNaive(words);

}

}

public static void testNaive(String[] words){

HashMap counter = new HashMap();

for (String w : words) {

if(counter.containsKey(w)){

int oldValue = counter.get(w);

counter.put(w, oldValue+1);

} else {

counter.put(w, 1);

}

}

}

// 可变Integer

public static final class MutableInteger{

private int val;

public MutableInteger(int val){

this.val = val;

}

public int get(){

return this.val;

}

public void set(int val){

this.val = val;

}

// 为了方便打印

public String toString() {

return Integer.toString(val);

}

}

// 入门级计数器

public static void testBetter(String source, int loop){

if(null == source){

return;

}

//

String[] words = source.split(" ");

for (int i = 0; i < loop; i++) {

testBetter(words);

}

}

public static void testBetter(String[] words){

HashMap counter = new HashMap();

for (String w : words) {

if(counter.containsKey(w)){

MutableInteger oldValue = counter.get(w);

oldValue.set(oldValue.get()+1);// 因为是引用,所以减少了一次HashMap查找

} else {

counter.put(w, new MutableInteger(1));

}

}

}

// 卓越级计数器

public static void testEfficient(String source, int loop){

if(null == source){

return;

}

//

String[] words = source.split(" ");

for (int i = 0; i < loop; i++) {

testEfficient(words);

}

}

public static void testEfficient(String[] words){

HashMap counter = new HashMap();

for (String w : words) {

MutableInteger initValue = new MutableInteger(1);

// 利用 HashMap 的put方法弹出旧值的特性

MutableInteger oldValue = counter.put(w, initValue);

if(oldValue != null){

initValue.set(oldValue.get() + 1);

}

}

}

}

当你实用计数器的时候,很可能也需要根据值来进行排序的方法,请参考: 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 方法:):

HashMap efficientCounter2 = new HashMap();

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 atomicCounter = new HashMap();

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 intCounter = new HashMap();

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]++;

}

}

Guava 语言的 MultiSet 可能更快一些.

6. 结论

优胜者是使用int数组的方式.

参考文章

HashMap.put() HashMap.put()

相关阅读

1. ArrayList vs. LinkedList vs. Vector

Frequently Used Methods of Java HashMap

Hadoop中的计数器有点类似于日志，可以输出Hadoop在运行过程的运运算信息。

在之前运行的WordCount中，控制台输出的信息有以下内容(可以再运行一次WordCount案例进行查看)：Counters: 38

File System Counters #10个

FILE: Number of bytes read=462

FILE: Number of bytes written=541399

FILE: Number of read operations=0

FILE: Number of large read operations=0

FILE: Number of write operations=0

HDFS: Number of bytes read=38

HDFS: Number of bytes written=19

HDFS: Number of read operations=15

HDFS: Number of large read operations=0

HDFS: Number of write operations=6

Map-Reduce Framework #20个

Map input records=2

Map output records=4

Map output bytes=35

Map output materialized bytes=49

Input split bytes=109

Combine input records=0

Combine output records=0

Reduce input groups=3

Reduce shuffle bytes=49

Reduce input records=4

Reduce output records=3

Spilled Records=8

Shuffled Maps =1

Failed Shuffles=0

Merged Map outputs=1

GC time elapsed (ms)=59

CPU time spent (ms)=0

Physical memory (bytes) snapshot=0

Virtual memory (bytes) snapshot=0

Total committed heap usage (bytes)=242360320

Shuffle Errors #6个

BAD_ID=0

CONNECTION=0

IO_ERROR=0

WRONG_LENGTH=0

WRONG_MAP=0

WRONG_REDUCE=0

File Input Format Counters  #1个

Bytes Read=19

File Output Format Counters #1个

Bytes Written=19

可以看到输出的日志中，提示总共有38个计数器，分成了5组，File System Counters等称之为组名，可以看出每组分别有10、20、6、1、1个计数器。

对于这38个计数器，我们并不是每一个都关心，以下重点讲解部分计数器的作用

一、计数器讲解

1、File Input Format CountersFile Input Format Counters  #1个

Bytes Read=19

表示的是我们从HDFS中读取的文件的字节数总共是19个字节

回归之前的word.txt中的文本内容hello you

helo me

5+3+5+2=15，加上2个空格和一个换行，一个结束符也是19个字符。

2、Map-Reduce FrameworkMap-Reduce Framework #20个

Map input records=2

Map output records=4

Map output bytes=35

Map output materialized bytes=49

Input split bytes=109

Combine input records=0

Combine output records=0

Reduce input groups=3

Reduce shuffle bytes=49

Reduce input records=4

Reduce output records=3

Spilled Records=8

Shuffled Maps =1

Failed Shuffles=0

Merged Map outputs=1

GC time elapsed (ms)=59

CPU time spent (ms)=0

Physical memory (bytes) snapshot=0

Virtual memory (bytes) snapshot=0

Total committed heap usage (bytes)=242360320

Map input records=2hello you

hello me

刚好是2行

Map output records=4

由于我们的mapper中，是每读取一个单词，就输出一个键值对，因此map任务的输出是：,

,

,

刚好有四个

Reduce input records=4

map输出的记录就是reduce输入的记录数，因此也是四个

Reduce input groups=3

关于分组group的概念我们之后会详细讲解，实际上就是将mapper的输出的记录进行分组，即把相同key的分为一组，所以分组后是

刚好分成3组。

Reduce output records=3

WordCount案例中的输出为hello 2

you 1

me 1

刚好是3行。

Combine input records=0、Combine output records=0

这是属于规约，在后面我们会详细的讲解规约的概念。

二、自定义计数器

计数器用Counter对象表示，每个计数器都有一个组，只要组名(groupName)相同，那么这些计数器就自动属于一个组。并且每个计数器还有这自己的名字(counterName)，用以区分同一个组下的不同计数器。

获得一个计数器实例的方法如下：Counter counter = context.getCounter(groupName, counterName);

例如，我们现在要进行敏感词统计，即分析某段文本内容中出现了多少次敏感词。假设我们把"hello"认为是一个敏感词。在WordCount案例的基础上，我们可以将TokenizerMapper的代码修改如下public static class TokenizerMapper extends

Mapper {

private final static IntWritable one = new IntWritable(1);

private Text word = new Text();

@Override

public void map(LongWritable key, Text value, Context context)

throws IOException, InterruptedException {

// StringTokenizer是java工具类，将字符串按照空格进行分割

StringTokenizer itr = new StringTokenizer(value.toString());

//自定义计数器

String groupName="Custom Group";//

String counterName="Sensitive words";

Counter counter = context.getCounter(groupName, counterName);

// 每次出现一个单词，单词次数加1

while (itr.hasMoreTokens()) {

String nextToken = itr.nextToken();

if(nextToken.equals("hello")){//假设"hello"为敏感词，每次输出，即加1

counter.increment(1);

}

word.set(nextToken);

context.write(word, one);

}

}

}

再次运行WordCount案例，我们可以看到控制台中输出了我们自定义的计数器Counters: 39

File System Counters

FILE: Number of bytes read=462

FILE: Number of bytes written=541399

FILE: Number of read operations=0

FILE: Number of large read operations=0

FILE: Number of write operations=0

HDFS: Number of bytes read=38

HDFS: Number of bytes written=19

HDFS: Number of read operations=15

HDFS: Number of large read operations=0

HDFS: Number of write operations=6

Map-Reduce Framework

Map input records=2

Map output records=4

Map output bytes=35

Map output materialized bytes=49

Input split bytes=109

Combine input records=0

Combine output records=0

Reduce input groups=3

Reduce shuffle bytes=49

Reduce input records=4

Reduce output records=3

Spilled Records=8

Shuffled Maps =1

Failed Shuffles=0

Merged Map outputs=1

GC time elapsed (ms)=38

CPU time spent (ms)=0

Physical memory (bytes) snapshot=0

Virtual memory (bytes) snapshot=0

Total committed heap usage (bytes)=242360320

Custom Group #我们自定义的组名

Sensitive words=2 #我们自定义的计数器的值为2

Shuffle Errors

BAD_ID=0

CONNECTION=0

IO_ERROR=0

WRONG_LENGTH=0

WRONG_MAP=0

WRONG_REDUCE=0

File Input Format Counters

Bytes Read=19

File Output Format Counters

Bytes Written=19