#coding4fun#詞頻統計優化思路

關于這期的coding4fun，我選擇的是hashmap方式實作。整體思路和流程大家可能都差不多，C++同學們的總結寫的很好，一些邏輯優化都有總結，我這裡介紹下java實作的一些優化吧。

使用ByteString代替String

開始讀出檔案轉成String對象，然後通過String對象操作，代碼寫起來都比較友善。

但是有一個問題，檔案讀取出來的byte[]轉成String對象非常耗時，一個1G的String對象配置設定記憶體時間就很長了，String對象内部使用char[]，通過byte[]構造String對象需要根據編碼周遊byte[]。這個過程非常耗時，肯定是可以優化的。

于是我使用ByteString類代替String

class ByteString{
byte[] bs;
int start;
int end;
}      

hashcode()和equals()方法參考String的實作。

在code4fun的16核機器上測試如下代碼：

代碼1：

byte[] bs = new byte[1024*1024*1024];
long st = System.currentTimeMillis();
new String(bs);
System.out.println(System.currentTimeMillis() - st);  // 2619ms      

代碼2：

byte[] bs = new byte[1024*1024*1024];
long st = System.currentTimeMillis();
int count = 100000;
for(int i = 0; i < count; i++)
new ByteString(bs, 0, 100);
System.out.println(System.currentTimeMillis() - st);  //10ms      

循環中代碼要精簡

Hashmap的實作，給單詞計數時避免不了如下的代碼：

ByteString str = new ByteString(bs, start, end);
Count count = map.get(str);
If(count == null){
count = new Count(str,1);
map.put(str,count);
} else{
count.add(1);
}      

本來這段代碼沒什麼問題，但是當單詞個數足夠大的時候（最終1.1G的檔案，有2億多單詞），這段代碼就值得優化了。第一行建立的對象，隻有單詞第一次出現有用，其他時間都可以不用建立。

于是建立一個Pmap類，繼承HahsMap，并添加了一個get(ByteStringbs,intstart,intend)方法。上面的代碼改為

Count count = map.get(bs, start, end);
If(count == null){
ByteString str = new ByteString(bs, start, end);
count = new Count(str,1);
map.put(str,count);
} else{
count.add(1);
}      

能避免鎖就不用鎖，不能避免就減小範圍

concurrentHashMap的實作固然精妙，隻是能不用鎖盡量不用，實在用的時候，盡量減少範圍。CAS的方式雖然比鎖好，但是還是有消耗。

我們使用多線程的方式統計，是以統計結果對象需要線程安全。開始使用AtomicInteger，但是跟count++比起來效率還是差的非常多，單詞個數越多越明顯。

嘗試使用volatile關鍵字效果也是不理想，然後比不上count++。