单机环境，有大约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个小文件去重；此时得到结果
这是我想的一个简单办法，但是估算了一下时间可能要个把星期。。。好久
![[Web フロントエンド] Node.js クイック スタート](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
私は以前、数百ギガバイトの DNA シーケンスから反復シーケンスを削除するためにこれを実行したことがあります (ファイルの 1 行あたり 1 つのハッシュが 30G であると仮定します)。 1 日)、何をしているのかわかりません。この 512M はどれくらい続くのでしょうか...
あなたの方法に従って計算した 1 TB のデータの容量要件は、容量制限よりもはるかに大きいということを本当に理解しているかわかりませんが、時間はあなたの見積もりよりもはるかに短くなります。
最適なストレージ ソリューションとして MD5 を考慮すると、各 MD5 が占めるハードディスク容量は $$frac{log_{2}1632}{8}=16$$ となり、1TB のハード全体が占有します。ディスクには約 $$610^{10}$$ MD5 があります。
あなたの方法によると、平均的な状況では、占有スペースは 1TB/256 (4GB) となり、256MB の制限を超えます。さらに、MD5 の最初の 2 文字の分布は必ずしも均等ではないため、この値はさらに大きくなる可能性があります。
しかし、計算時間は、IO オーバーヘッドと分類の準備を考慮すると、約 16 時間であることがわかり、2 日を超えることはありません。
もちろん、理論的には、分類はそれほど面倒である必要はありません。外部で直接ソートし、重複を線形に削除する方が便利です。そして、メソッドの複雑さは $$O(nklog_{2}frac{n}{k})(k=256)$$ で、直接メソッドは $$O(nlog_{2}n)$$ です。理論的には、後者の方が複雑性も低くなります。ただし、ディスク IO などの要因があるため、どちらが優れているかについて結論を出すことはできません。
いわゆる
Hadoop を直接使用することはできますか~
ハッシュ値は 128 ビットです。1 ビットが異なっていれば重複しません。
したがって、あまり複雑な比較アルゴリズムを使用する必要はなく、一部を抽出して比較するだけで済みます。
たとえば、各ハッシュ値の下位 64 ビットのみを比較します。これにより、ほとんどの値が除外されます。
読み取りと書き込みの競合を避けるために、ハードディスクを 2 台使用するのが最善です。
2 番目の空のハードディスクは、A ディスクからハッシュ値をコピーする代わりに、重複値をマークするためのフラット スペースとして使用されます。
1. この種の質問は、面接や筆記試験の質問などで非常に頻繁に現れると思います。通常、
Googleで簡単に検索すると、より詳細な回答が見つかります。2.
hashこのアルゴリズムは、重複Bloom Filterを削除するために使用する必要があります。これにはブルーム フィルターを使用する必要があります
今のところ、IO 速度を無視するアルゴリズムを紹介します。
データを 1024 2 または 1024 2.5 に均等に分割します。
各データ ファイルのハッシュ値をソートし、O(NlogN) で簡単にソートするだけで十分です。
小さなルート ヒープを作成し、ファイルごとに 1 つずつ、1024 * 2.5 のファイル読み取り接続を確立します。
初めて、ファイルから 1024 * 2.5 の md5 を読み取り、それらを順番にヒープに置きます。各 md5 がどのファイルから来たのかをマークする必要があります。
ヒープの先頭を取り出して保存用のファイルに出力します (この md5 は計算が終了したことを意味します)。ただし、ヒープの先頭を最初に保持します。
4 番目に記録されたファイルに従って、そのファイルから別のファイル (1 つの md5 は複数のファイルに対応する可能性があります。複数ある場合は任意のファイルに対応します) をヒープに置き、新しいファイルを更新します。 md5 はどのファイルからのものですか;
ヒープの先頭を取り出し、レコード 5 の以前のヒープの先頭と比較します。それらが同じである場合は破棄し、異なる場合はファイルに保存し、レコードを更新します。ヒープの一番上に配置し、6 に進みます。全キャラ完成するまで。 O(NlogN)
合計平均複雑さ: O(NlogN)。
ここでいくつかの疑問があります。まず、これほど大きな配列を開いたことがないので、一度に 0.5 G のデータをメモリに配置できるかどうかがわかりません。次に、辞書ツリーを使用できるかどうかです。問題を解決します。パート 4 の録画速度が速くなります。 、 読み取り用に数千のファイルストリームを作成できるかどうかはわかりません。作成できない場合は、次のようなものを作成できます。毎回 1 つの md5 を読み取ると、1 TB を読み取ろうとすると、許容できないほど遅くなりますか?
IO が遅すぎる場合、このメソッドは数日間実行される可能性があります。