1

データのファイルが2つあり、それぞれ100文字の行があります。ファイルA：10 8行、ファイルB：106行。そして、ファイルAにないファイルBのすべての文字列を見つける必要があります。最初は、両方のファイルをmysqlにフィードすることを考えていましたが、 108レコード
で一意のキーを作成し終えることはないようです。

これについてのご提案をお待ちしております。

4

3 に答える 3

5

この操作はデータベースなしで実行できます。AはBよりもはるかに大きいため、重要なのはAのサイズを小さくすることです。これを行う方法は次のとおりです。

Bファイルの文字列に対して適切なハッシュ関数を使用して64ビットハッシュを計算します。これらをメモリ（ハッシュテーブル）に保存します。これは、Bが小さいため実行できます。次に、Aファイル内のすべての文字列を1行ずつハッシュし、それぞれがBファイルのハッシュと一致するかどうかを確認します。ハッシュが一致する行（Bから1行まで）は、ファイルCに保存する必要があります。

このプロセスが完了すると、ファイルCには、（Bに対して）一致する可能性のある文字列のAの小さなサブセットが含まれます。これで、Bの行を比較する必要があるはるかに小さいファイルCができました。これにより、問題がCからメモリに（ハッシュテーブルとして）実際にすべての行をロードし、Bの各行を比較してCにあるかどうかを確認できる問題になります。

于 2010-10-13T18:23:49.450 に答える
3

@ michael-goldshteynの回答（https://stackoverflow.com/a/3926745/179529）を少し改善できます。AにないBのすべての文字列を見つける必要があるため、Aの要素と比較して一致するものを見つけると、Bの要素のハッシュテーブルから任意のアイテムを削除できます。ハッシュテーブルに残っているのは、ファイルAで見つからなかった要素です。

于 2012-02-03T14:37:16.643 に答える
1

あなたが言及するサイズについては、Bのすべてを一度にメモリに保持できるはずです。そうすれば、Goldshteynの答えの簡略化されたバージョンを実行できます。Pythonでこのようなもの：

#!/usr/bin/python3

import sys

if __name__=='__main__':
  b = open(sys.argv[2],'r')
  bs = set()
  for l in b:
    bs.add(l.strip())
  b.close()
  a = open(sys.argv[1],'r')
  for l in a:
    l = l.strip()
    if l in bs:
      bs.remove(l)
  for x in bs:
    print(x)

私はこれを10^5と10^7のサイズの2つのファイルでテストし、アトムプロセッサで1行あたり最大8文字を使用しました。/ usr / bin / timeからの出力：

25.15user 0.27system 0:25.80elapsed 98%CPU (0avgtext+0avgdata 56032maxresident)k
0inputs+0outputs (0major+3862minor)pagefaults 0swaps
  60298   60298  509244
于 2010-10-13T19:19:24.347 に答える