私は取り除きたいすでに

Question

は私が

は、その後、私は別の大きなファイル「post.txtを」持っている「done.txt」大きなファイルを持っていると言う別の行に含まれているすべての行を削除する方法既にdone.txtにあるpost.txt内のすべての出現

私はdone.txtのすべてのコンテンツをメモリにロードしたくありません。どうすればいい？

精度は重要ではありません。

Answer 1

100％の精度は必須ではないので、すべての行をdone.txtにハッシュし、それらのハッシュのコレクション（配列、リストなど）をメモリ内に保持できます。

次に、すべての行をpost.txtに処理します。その行のハッシュが既に持っているものと一致する場合は、それを放棄してください。

ではなくではないにもかかわらず、偽陽性がありますが、偽陰性はありません。

ような何か：

hash = [] 

for each line in done.txt: 
    hashVal = makeHash (line) 
    hash[hashVal] = true 

for each line in post.txt: 
    hashVal = makeHash (line) 
    if not defined hash[hashVal]: 
     print line 

それとも、あなたは最小限のメモリ内のストレージと100％の精度が必要な場合は、ハッシュあたりのファイルオフセットのコレクションと一緒にハッシュを保ちます。

post.txtの行がいずれのハッシュとも一致しない場合は、重複している可能性はないのでそのまま使用してください。

の場合、はハッシュと一致し、の可能性があります。は重複しています。そのハッシュエントリに対して1つまたは複数のファイルオフセットを使用して、実際の行を読み取って、done.txtの行に対してテストされている行のバイナリ比較を実行します。そこにマッチが見つかった場合は、そのママがそのラインを投げ捨てるので、そうしないとあなたはそれを保持します。

これは、ハッシュ付きラインオフセットコレクションと、最大でdone.txtからの1行のat-memoryストレージ（もちろん、post.txtの行以外は必要ですが）を削減します。潜在的な余分なI/Oのコスト。

しかし、私は「100％精度未満」という大きなファンではないので、それはおそらく行くだろう。

hash = [] 

fileOffset = 0 
for each line in done.txt: 
    hashVal = makeHash (line) 
    if not defined hash[hashVal]: 
     hash[hashVal] = new list() 
    hash[hashVal].append (fileOffset) 
    fileOffset = fileOffset + line.length() 

for each line in post.txt: 
    hashVal = makeHash (line) 
    printIt = true 
    if defined hash[hashVal]: 
     for each offset in hash[hashVal]: 
      read chkLine from done.txt starting at offset 
      if line == chkLine: 
       printIt = false 
    if printIt: 
     print line