確定大文件中的字符串唯一性

在C中，我想處理一個文件，其中包含10位數字的字母數字字符串，並確定每個文件在文件中是否唯一。我怎樣才能做到這一點？確定大文件中的字符串唯一性

來源

2010-08-13 venkat

到目前爲止您嘗試過什麼？你在哪裏遇到問題？我們不是代碼猴子。 – 2010-08-13 21:20:29

你需要確定每一個是唯一的，還是隻提取獨特的？ – 2010-08-13 21:32:47

你有多少內存？只需存儲標識符大約需要800MB。如果你能夠承受大約兩倍的使用，任何合理的數據結構（哈希表，平衡樹，trie）都可以。否則，你需要更聰明。 – Gilles 2010-08-13 21:33:43

鑑於您所談論的是大約16兆字節的數據，顯而易見的方法是將數據加載到哈希表（或該順序上的某些內容）並計算每個字符串的出現次數。

我不能完全想象用C，雖然這樣做 - 大多數其他語言將提供一個合理的數據結構（某種地圖），使工作明顯更容易。

來源

2010-08-13 21:29:55

嗯任何相同的字符串，它是多一點，然後16兆根據我的數學:) – 2010-08-13 21:35:50

16 * 10^8〜是16 GB – 2010-08-13 21:36:18

你能算數人，爲了圖靈的緣故嗎？ – 2010-08-13 21:38:09

您需要對文件進行排序。

只需將其加載到一個內存塊中，從內存塊上的C運行時庫運行qsort，然後依次在所有字符串上運行以檢查兩個相同的連續字符串。

來源

2010-08-13 21:33:23 Codo

我不得不不同意。對n元素數組進行排序是O（n log n），而填充散列表或散列集是將O（n）攤銷。在這個尺寸的數據上，這是一個實際的區別。 – 2010-08-13 21:41:38

@Matthew：但是，我們在這裏談論的內容大約是1.6GB，可能空間有限。對數據進行排序只需要一點額外的內存就可以完成，而散列會需要更多的數據。如果有足夠的可用內存（如內存不足的內存充足的64位系統），請執行散列操作。否則，就地排序可能比涉及磁盤緩存的解決方案更快（或者可能不;日誌1.6G相當大）。 – 2010-08-13 22:24:22

@大衛，這是一個有效的點。常數因素（包括交換到磁盤）總是會影響運行時間。但是再一次，'log2（10^8）'是26.無論如何，「需要」對它進行排序當然不是真的。散列至少需要考慮。 – 2010-08-14 03:57:09

帶有設置/地圖功能的圖書館，例如見link text

來源

2010-08-13 21:37:49 user411313

@all我不知道任何數據結構，我的意思是我知道的基本知識........我想搜索每個ID是否是獨特的或不是從1000萬字符串.......... ..... – venkat 2010-08-14 18:45:40

正如其他人所說，最直接的方法是簡單地加載整個文件，並使用像qsort這樣的東西來排序它。

如果你不能一次加載多少內存到另一個內存中，另一個選擇是通過多次加載數據。在第一遍時，讀取該文件並僅加載以A開頭的行。對這些排序並找到唯一的行。對於下一步，加載所有以B開頭的行，進行排序並找到唯一的行。對於每行可能以字母開頭的字母數字字符重複此過程。使用這種技術，您應該只需將文件的一部分一次加載到內存中，並且不應該導致您對任何行進行錯誤分類。

來源

2010-08-13 21:39:54 bta

對一個存儲桶執行一個存儲桶排序（散列函數）爲多個文件，一個文件。然後處理每個存儲桶的文件，以確定存儲桶中的所有字符串是否都是唯一的。

來源

2010-08-13 21:48:32 Mike

確定大文件中的字符串唯一性

回答

相關問題