找到兩個相同的文件行

我在亞馬遜採訪中被問到這個問題。找到兩個相同的文件行

你有一個文件有許多行，但其中兩行是相同的。找到這兩條線。我給出了在N^2時間內運行的明顯答案。然後我想出了一個使用哈希表的答案，但他們不喜歡那個答案，要麼是因爲他們說如果文件是千兆字節就不行。我想出的另一個答案是將哈希結果存儲在內存中，創建一個與哈希值名稱相同的文件，並將具有相同哈希值的行存儲在文件中。要麼他們不明白我的解決方案，或者他們不喜歡它。

有什麼想法？

謝謝

來源

2012-12-06 John Smith

對於Linux，很容易'sort | uniq -c | grep'^ 2'' –

好吧，讓我看看其他的解決方案，但是不會將這些文件sl into到內存中嗎？ –

@JohnSmith：當數據不適合內存時，GNU'sort'知道如何進行外部排序（http://vkundeti.blogspot.co.uk/2008/03/tech-algorithmic-details-of-unix -sort.html）。 –

我能想到的解決方案的兩個基本類別的這個問題：

概率的內存解決方案。您可以嘗試通過在主內存中存儲文件行的摘要來解決此問題。然後，您可以在主內存中執行計算以識別可能的重複項，然後通過回顧磁盤檢查每個可能的重複項。這些解決方案可能是最好的，因爲它們具有較低的內存使用率，較高的效率和較小的磁盤訪問。此類別的解決方案包括：
1. 計算文件每一行的散列，然後存儲散列。任何具有散列衝突的行代表可能發生碰撞的一對可能的行，並且可以探索這些行。
2. 使用Bloom Filter存儲文件的所有行，然後只檢查在Bloom Filter中發生衝突的對。這實質上是（1）的變體，它更節省空間。
確定性磁盤上解決方案。您可以嘗試使用磁盤上的整個數據集進行計算，將主內存用作臨時臨時空間。這可以讓你得到確切的答案，而不必將整個文件保存在內存中，但可能會更慢，除非你稍後進行一些處理並可以從數據重構中受益。此類別中的解決方案包括
1. 使用外部排序算法（外部快速排序，外部基數排序等）的文件進行排序，然後線性搜索它用於一對重複的元件。
2. 構建一個像B樹一樣的磁盤數據結構來存放所有的字符串，然後查詢B樹。這需要很多預處理時間，但是使得文件的未來操作速度更快。
3. 將所有內容放入數據庫並查詢數據庫。

希望這有助於！

來源

2012-12-06 21:40:49 templatetypedef

外部排序似乎是最直接的解決方案。一種優化是當你排序時，你可以確定重複項，併合並塊，因此可能不得不對整個文件進行排序。 –

我會把這個標記爲正確的答案，因爲它有很多正確的答案，我在那裏學到了一些新東西，尤其是外部排序和Bloom Filters。 –

通過行和計算每一行的長度。你會得到類似的結果：

0: 4 
1: 6 
2: 10 
3: 4 
....

只比較具有相同長度的thoose行。使用這樣的索引可以進一步優化（例如，不是將所有內容都存儲在平面數組中，而是存儲在某種樹中，或者其他任何內容中）。

順便說一下，由於性能原因，您對文件的第二個想法可能會被拒絕。在硬盤上頻繁使用隨機IO通常是個不好的主意：儘量在內存中存儲。

來源

2012-12-06 21:34:06

我認爲這是一個優雅的解決方案，但他們可能會抱怨說你不得不使用額外的內存。當然，如果文件有許多相同大小的行，則會遇到問題。 –

您可以使用Bloom過濾器：

http://en.wikipedia.org/wiki/Bloom_filter

然後你就可以檢測（用幾個假陽性）被重複的線，然後存儲在內存中，然後經過文件再次。

兩次通過該文件，很少的內存使用量，美麗

來源

2012-12-06 21:35:03 tjltjl

第二遍不一定是順序的不是嗎？如果我們存儲每行的位置以及我相信的散列，就可以用一堆fseek（）調用完成。 –

不，重點在於，如果您存儲位置，則存儲的數量比Bloom過濾器存儲的每個條目的位數要多。 – tjltjl

我明白了，我誤解了布盧姆過濾器。謝謝！ –

找到兩個相同的文件行

回答

相關問題