作者ewn (...)
看板java
標題Re: [問題] hashmap 的效能 (300mb檔案)
時間Thu Sep 6 21:20:25 2012
大概看了一下你的需求
有點類似要將2個文字檔做join的意思
實務上我們也常常做這樣的事情
常常也是幾十、幾百mb的文字檔在結合
一開始，我的想法跟你一樣：
「用HashMap，用hash取值很快呀」
事實證明，我錯了…
小小的資料量和複雜的資料結構，也許Map很適合
但如果是要做你這樣的需求
先不考慮記憶體大小，光是用演算法教的複雜度去計算
這都是一個複雜度很高的動作
(建map先不考慮，光是從Map取值，就要千萬次，不慢才怪)
後來發現，最笨的方法或許最實用，說穿了不值錢
不過這是老一輩寫cobol的人最愛用的方法，就是：
「先排序了再來」
只要先將2個檔案，依照要結合的key值做排序
之後同時讀取2個檔案，邊讀邊比較2邊的key邊進行結合
2個檔案都是O(N)的複雜度
每一列僅需讀取一次，即可結合完成
這種方法，不僅速度足夠快，而且需要的記憶體也不多
唯一的缺點就是：「方法很笨，還產出一個文字檔」
P.S. 請使用現成的sort utility，ex: gnu sort，windows下可裝cygwin之類的環境
舉例來說
你有2個檔案如下所示，A檔有3個column，B檔有4個column，以空白分隔：
A(a1,a2,a3)，B(b1,b2,b3,b4)
假設你要結合的key是b2和a1，結合步驟如下：
sort -k 1 A > A'
sort -k 2 B > B'
java some.MergeProgram A' B' > C
MergeProgram做的事僅是分別讀取A'及B'
比較a1和b2，一樣就結合輸出，不一樣就依照大小、判斷要讀哪邊的檔
參數及寫法要依照你實際的需求進行調整，上述僅是說明用
僅供參考
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.24.108.201
1F：→ bitlife:基本上把hash map換成tree map就有讀完就排好的效果了 09/06 21:22
2F：→ ewn:重點是，千萬筆資料，建成TreeMap，Memory就爆了... 09/06 21:23
3F：推 LPH66:這其實就只是 Mergesort 而已... 09/06 23:14
4F：→ bitlife:sort除非你用外部排序,不然一樣有記憶體問題.現在記憶體都 09/06 23:21
5F：→ bitlife:nG的,先解決問題再說吧 09/06 23:23
6F：推 zephyrhymn:資料量大時，Map還是比List快吧，不過同樣是記憶體問題 09/07 00:56
7F：→ zephyrhymn:但現在記憶體便宜，64bits的JAVA爽爽用 09/07 00:57
8F：推 gmoz:架hadoop cluster來跑mpa/reduce啦 (誤 09/07 12:55