作者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