從一個大文件中找到唯一值

我有一個大文件（比如10TB）和MD5哈希流（包含重複項），我給了10MB（非常有限）和無限硬盤空間的內存。使用給定的條件查找所有獨特的哈希（消除重複）。請幫助，這顯然不是一個作業問題從一個大文件中找到唯一值

2013-05-16 username

「這顯然不是一個功課問題」 –

性能是否重要？我的意思是可以使用一些O（n^2）解決方案嗎？ – Fingolfin

@AdelQodmani對於10 * terabytes *值的16字節散列，O（n^2）和O（n * logn）之間的性能差異是天文數字。 – Andrei

您可以使用外部排序算法（例如，使用polyphase merge sort）對散列進行排序，之後您只需遍歷文件並跳過等於最新散列的散列

hash mostRecentHash; 
while(fileHasHashes) { 
    temp = fileWithDuplicates.readHash(); 
    if(!hashesAreEqual(mostRecentHash, temp)) { 
     mostRecentHash = temp; 
     fileWithoutDuplicates.writeHash(mostRecentHash); 
    } 
}

來源

2013-05-16 21:56:05

外部多相合並排序是這個的完美算法。 +1 –

+1刪除我的答案，因爲這是一個更好的解決方案。 – idz

那他爲什麼要求我使用無限數據庫？ – username

如果性能並不重要，你的文件系統是沒有限制的，那麼你可以簡單地創建爲每個哈希的文件。如果在創建過程中遇到EEXIST，那麼你有一個副本，它可以被跳過。

for (each hash) { 
    r = open(hash_to_filename(hash), O_CREAT|O_EXCL); 
    if (r < 0) { 
     if (errno == EEXIST) continue; 
     perror(hash); 
     exit(EXIT_FAILURE); 
    } 
    close(r); 
    output(hash); 
}

這樣做的好處是它保留了流中第一次出現散列值的順序。

該解決方案的實際性能取決於文件系統的性能。如果文件在B-Tree中組織，則性能將大致爲O（N log（N））。如果文件系統使用散列表來組織文件，則性能預期爲O（N），但這取決於發生衝突的頻率（以及由於磁盤訪問導致的常數因子很高）。

來源

2013-05-16 22:08:12 jxh

這顯然不是一個壞的解決方案。 –

我喜歡Zim-Zam的解決方案......提出一個小的變化。

如果我們可以假設指紋在128位空間上均勻分佈，那麼我們可以使用像Bucket sort之類的東西來將指紋分成（更小）的桶文件，單獨對桶文件進行排序，然後合併使用堆將文件存儲到一個排序文件中？這可能會降低成本。

來源

2013-05-17 22:10:28 lsk

從一個大文件中找到唯一值

回答

相關問題