天天看點

#coding4fun#詞頻統計優化思路

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

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

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

于是我使用bytestring類代替string

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

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

代碼1:

代碼2:

hashmap的實作,給單詞計數時避免不了如下的代碼:

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

于是建立一個pmap類,繼承hahsmap,并添加了一個get(bytestring bs, int start, int end)方法。上面的代碼改為

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

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

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

最後使用兩個字段來解決這個問題:線上程内部統計單詞個數時,使用count++方式;到合并環節,單詞數已經不多,使用atomicinteger的方式累加,基本不影響效率。

通過減少鎖的範圍和鎖的次數,來達到提升效率的目标。