亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

Efficient Counter in Java

系統(tǒng) 1741 0

Reference: ?http://www.programcreek.com/2013/10/efficient-counter-in-java/

?
You may often need a counter to understand the frequency of something (e.g., words) from a database or text file. A counter can be easily implemented by using a HashMap in Java. This article compares different approaches to implement a counter. Finally, an efficient one will be concluded.

UPDATE: Check out? Java 8 counter , writing a counter is just 2 simple lines now.

1. The? Naive ?Counter

Naively, it can be implemented as the following:

String s = "one two three two three three";String[] sArr = s.split(" ");?//naive approach HashMap<String, Integer> counter = new HashMap<String, Integer>();?for (String a : sArr) { if (counter.containsKey(a)) { int oldValue = counter.get(a); counter.put(a, oldValue + 1); } else { counter.put(a, 1); }}

In each loop, you check if the key exists or not. If it does, increment the old value by 1, if not, set it to 1. This approach is simple and straightforward, but it is not the most efficient approach. This method is considered less efficient for the following reasons:

  • containsKey(), get() are called twice when a key already exists. That means searching the map twice.
  • Since Integer is immutable, each loop will create a new one for increment the old value

2. The? Better ?Counter

Naturally we want a mutable integer to avoid creating many Integer objects. A mutable integer class can be defined as follows:

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; }? //used to print value convinently public String toString(){ return Integer.toString(val); }}

And the counter is improved and changed to the following:

HashMap<String, MutableInteger> newCounter = new HashMap<String, MutableInteger>(); ?for (String a : sArr) { if (newCounter.containsKey(a)) { MutableInteger oldValue = newCounter.get(a); oldValue.set(oldValue.get() + 1); } else { newCounter.put(a, new MutableInteger(1)); }}

This seems better because it does not require creating many Integer objects any longer. However, the search is still twice in each loop if a key exists.

3. The? Efficient ?Counter

The HashMap.put(key, value) method returns the key's current value. This is useful, because we can use the reference of the old value to update the value without searching one more time!

HashMap<String, MutableInteger> efficientCounter = new HashMap<String, MutableInteger>();?for (String a : sArr) { MutableInteger initValue = new MutableInteger(1); MutableInteger oldValue = efficientCounter.put(a, initValue);? if(oldValue != null){ initValue.set(oldValue.get() + 1); }}

4. Performance Difference

To test the performance of the three different approaches, the following code is used. The performance test is on 1 million times. The raw results are as follows:

Naive Approach : 222796000Better Approach: 117283000Efficient Approach: 96374000

The difference is significant - 223 vs. 117 vs. 96. There is huge difference between? Naive ?and? Better , which indicates that creating objects are expensive!

String s = "one two three two three three";String[] sArr = s.split(" ");?long startTime = 0;long endTime = 0;long duration = 0;?// naive approachstartTime = System.nanoTime();HashMap<String, Integer> counter = new HashMap<String, Integer>();?for (int i = 0; i < 1000000; i++) for (String a : sArr) { if (counter.containsKey(a)) { int oldValue = counter.get(a); counter.put(a, oldValue + 1); } else { counter.put(a, 1); } }?endTime = System.nanoTime();duration = endTime - startTime;System.out.println("Naive Approach : " + duration);?// better approachstartTime = System.nanoTime();HashMap<String, MutableInteger> newCounter = new HashMap<String, MutableInteger>();?for (int i = 0; i < 1000000; i++) for (String a : sArr) { if (newCounter.containsKey(a)) { MutableInteger oldValue = newCounter.get(a); oldValue.set(oldValue.get() + 1); } else { newCounter.put(a, new MutableInteger(1)); } }?endTime = System.nanoTime();duration = endTime - startTime;System.out.println("Better Approach: " + duration);?// efficient approachstartTime = System.nanoTime();?HashMap<String, MutableInteger> efficientCounter = new HashMap<String, MutableInteger>();?for (int i = 0; i < 1000000; i++) for (String a : sArr) { MutableInteger initValue = new MutableInteger(1); MutableInteger oldValue = efficientCounter.put(a, initValue);? if (oldValue != null) { initValue.set(oldValue.get() + 1); } }?endTime = System.nanoTime();duration = endTime - startTime;System.out.println("Efficient Approach: " + duration);

When you use a counter, you probably also need a function to sort the map by value. You can check out? the frequently used method of HashMap .

5. Solutions from Keith

Added a couple tests:
1) Refactored "better approach" to just call get instead of containsKey. Usually, the elements you want are in the HashMap so that reduces from two searches to one.
2) Added a test with AtomicInteger, which michal mentioned.
3) Compared to singleton int array, which uses less memory according to http://amzn.com/0748614079

I ran the test program 3x and took the min to remove variance from other programs. Note that you can't do this within the program or the results are affected too much, probably due to gc.

Naive: 201716122Better Approach: 112259166Efficient Approach: 93066471Better Approach (without containsKey): 69578496Better Approach (without containsKey, with AtomicInteger): 94313287Better Approach (without containsKey, with int[]): 65877234

Better Approach (without containsKey):

HashMap<String, MutableInteger> efficientCounter2 = new HashMap<String, MutableInteger>();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)); } }}

Better Approach (without containsKey, with AtomicInteger):

HashMap<String, AtomicInteger> atomicCounter = new HashMap<String, AtomicInteger>();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)); } }}

Better Approach (without containsKey, with int[]):

HashMap<String, int[]> intCounter = new HashMap<String, int[]>();

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's MultiSet is probably faster still.

6. Conclusion

?

The winner is the last one which uses int arrays.

Efficient Counter in Java


更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號(hào)聯(lián)系: 360901061

您的支持是博主寫(xiě)作最大的動(dòng)力,如果您喜歡我的文章,感覺(jué)我的文章對(duì)您有幫助,請(qǐng)用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點(diǎn)擊下面給點(diǎn)支持吧,站長(zhǎng)非常感激您!手機(jī)微信長(zhǎng)按不能支付解決辦法:請(qǐng)將微信支付二維碼保存到相冊(cè),切換到微信,然后點(diǎn)擊微信右上角掃一掃功能,選擇支付二維碼完成支付。

【本文對(duì)您有幫助就好】

您的支持是博主寫(xiě)作最大的動(dòng)力,如果您喜歡我的文章,感覺(jué)我的文章對(duì)您有幫助,請(qǐng)用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長(zhǎng)會(huì)非常 感謝您的哦!!!

發(fā)表我的評(píng)論
最新評(píng)論 總共0條評(píng)論
主站蜘蛛池模板: 欧美一级亚洲一级 | 全部免费特黄特色大片视频 | 青青青青久久国产片免费精品 | 色综合久久久久久久久五月 | 一级肉体毛片视频免费看看 | 四虎永久成人免费 | 午夜国产福利在线观看 | 欧美日本视频一区 | 中文字幕精品在线 | 国模极品一区二区三区 | 国产免费人成在线视频视频 | 欧美日韩一二三区 | 成人在线第一页 | 精品一久久香蕉国产线看播放 | 老子影院我不卡 | 精品久久久久久久九九九精品 | 中文字幕在线观看日本 | 免费中文字幕在线观看 | 日本特黄a级高清免费大片18 | 最新国产福利片在线观看 | 三级性生活视频 | 亚洲视频一区在线观看 | 视频毛片 | 欧美亚洲另类综合 | 国产三级久久 | 天天爽夜夜爽天天做夜夜做 | 羞羞色院91蜜桃在线观看 | 久热99这里只有精品视频6 | 不卡精品国产_亚洲人成在线 | 久久亚洲私人国产精品 | 成人午夜影院在线观看 | 日日碰日日摸日日澡视频播放 | 国产精品夜色视频一级区 | 天天干天天色天天射 | 日本高中生一级乇片 | 国产成年人在线观看 | 美女被羞羞视频网站在线 | 欧美另类高清xxxxx | 成年性午夜免费视频网站不卡 | 97影院理论午夜论不卡 | 美女视频很黄很暴黄是免费的 |