Rumah > Soal Jawab > teks badan
单机环境,有大约1TB硬盘装满了md5哈希,里边有重复的,怎样才可能最快速度踢出重复的。内存大小限定为512MB吧
我实际遇到的一个问题,我去知乎提问了。居然被管理员封了,说我“代为解决个人问题”
https://www.zhihu.com/questio...
我把我知乎的回复抄过来
居然有人投诉说"代为完成个人任务",也是醉了。这个问题不是面试题,也不是啥个人问题。是我实实在在遇到的问题。我有个思路,实现也简单,但是预估计跑完得个把星期了。
现在有两T,1TB是数据,另外1TB用来存放结果。
我现在没有啥特别好的思路。只有最简单的优化。
分文件
A分区存1TB数据,B分区空闲
MD5hash 特点0~9a-f 总共16种情况 总共32个字符。
第一步分级
分两级
第一级 0·f 总公16个目录
第二级 0-f 总共16 个文件
那么这样下来我们总共会有256个文件
从A分区中顺序读取哈希,哈希的第一个字母情况根据目录进行分类;
哈希的第二个字母进行文件分类;对于任意一个A分区中的数据,会通过前两个字母定位
到这256个文件中的某一个;
顺序遍历A分区数据,完成全部操作之后会生成256个文件。
第二步
此时就转化成为将256个小一点的文件进行去重;
对于小一点的文件去重;
分块读入内存进行堆排序,进行一次顺序遍历则可以剔除重复数据;
对于两个已经分块的顺序数据合并去重;这种情况相当于“”有序单链表合并问题“”
很容易做到;
依次重复1.2两步可以将这256个小文件去重;此时得到结果
这是我想的一个简单办法,但是估算了一下时间可能要个把星期。。。好久
黄舟2017-04-17 14:44:33
之前做过去除几百G的DNA序列中的重复序列,感觉和这个问题类似(假设你的文件一行一个hash),buffsize给的是30G(在集群上跑了一天),不知道你这个512M要跑多久...
sort -u -S buffsize -o unique_file file
巴扎黑2017-04-17 14:44:33
不知我是否对那1TB数据真正理解,我按你的方法算出来的空间要求远大于你的空间限制,但时间远小于你的估计。
考虑MD5为最优存储方案,则每个MD5占用的硬盘空间为$$frac{log_{2}1632}{8}=16$$,如此,整个1TB硬盘中约有$$610^{10}$$个MD5。
按你的方法,在平均情况下,空间占用为1TB/256(4GB),超过了256MB的限制。何况MD5首两个字母的分布不一定是平均的,所以这个值可能会更大。
但是计算时间,我得出来的答案约为16h,算上IO的开销及分类准备,怎么也不可能超过两天。
当然,理论上分类没必要这么麻烦,直接外部排序并线性去重来的更方便。且你的方法复杂度为$$O(nklog_{2}frac{n}{k})(k=256)$$,直接方法为$$O(nlog_{2}n)$$,所以在理论复杂度上后者也更低。但是加上磁盘IO等因素,孰优孰劣我可不能妄加定论了。
所谓
ringa_lee2017-04-17 14:44:33
直接用Hadoop行不行~
哈希值是128位的,只要其中1位不同,就不是重复的。
所以,不用太复杂的比较算法,只要抽取其中一部分进行比对就行了。
比如,只比较每个哈希值的低64位。这样能过滤掉大部分值。
硬盘最好是2个,避免读写冲突。
第二个空硬盘当作平坦空间用,用来标记重复值,而不是把哈希值从A盘复制出来。
PHPz2017-04-17 14:44:33
1.我觉得这类问题出现频率很高的,比如面试,笔试题中,所以一般Google
一把,都能找到比较详细的答案的。
2.hash
去重应该可以用这个算法Bloom Filter
怪我咯2017-04-17 14:44:33
我来一个暂且忽略IO速度的算法:
把数据平均分成1024 2或 1024 2.5个;O(N)
对每个数据文件的hash值进行排序,快排就可以了; O(NlogN)
建立一个小根堆,然后建立1024 * 2.5个文件读取连接,一个文件对应一个;
第一次先从文件中读取1024 * 2.5个md5,依次放到堆中,得标记一下每个md5是来自哪一个文件;
将堆顶取出,输出到文件中存储(这个md5代表算完了),但这个堆顶先留着;
根据4记录的文件,从那个文件(有可能一个md5对应了多个文件,如果有多个,随便一个文件就行)再读1个放进堆中,并更新一下新的md5是来着哪个文件;
将堆顶取出,与5记录的前堆顶进行比较,如果相同的则抛弃;如果不同,则存入文件,并更新堆顶的记录,转到6。直到所有字符都搞完了。O(NlogN)
总平均复杂度:O(NlogN)。
现在有这样几个问题,一,我不清楚0.5个G的数据能不能在内存中一次性排完,因为我没开过那么大的数组;二,如果会使用字典树来解决第4部的记录那速度会更快;三,能不能建立几千个文件流来读我也不清楚,没试过,如果建立不了,可以建1个也行;四,IO输入输出会不会很慢,比如每次读1条md5,要读1TB的,会不会慢到无法接受。
IO太慢的话,这个方法跑上好几天也是可能的。