[解決済み] [Solved] あるファイルにある行を別のファイルにない行を見つける速い方法？

質問

私は2つの大きなファイル（ファイル名のセット）を持っています。それぞれのファイルでおよそ30,000行です。私は、ファイル2に存在しないファイル1内の行を見つけるための高速な方法を見つけようとしています。

例えば、これが ファイル1:

line1
line2
line3

そして、これは ファイル2です。

line1
line4
line5

それから、私の 結果/出力 となるはずです。

line2
line3

これは有効です。

grep -v -f file2 file1

しかし、私の大きなファイルで使用すると、非常に、非常に遅いです。

を使って行う良い方法があるのではないかと思っています。 diff() という出力になるはずですが ちょうど 行だけで、他には何もないのですが、そのためのスイッチが見つからないようです。

どなたか、bashと基本的なLinuxのバイナリを使って、これを行う高速な方法を見つけるのを助けてくれませんか？

EDIT : 私自身の質問のフォローアップとして、これは私がこれまでに見つけた最良の方法です。 diff() :

 diff file2 file1 | grep '^>' | sed 's/^>\ //'

きっと、もっといい方法があるはずだ。

どうすれば解決するの？

これは、旧行/新行/変更行の書式をGNUで制御することによって実現できます。 diff を出力します。

diff --new-line-format="" --unchanged-line-format=""  file1 file2

入力ファイル はソートされている必要があります。 を使用します。とは bash (そして zsh を使用すると、プロセス置換を使用してインプレースでソートできます。 <( ) :

diff --new-line-format="" --unchanged-line-format="" <(sort file1) <(sort file2)

上記の中で 新規 と 変更なし の行は抑制されるので 変更 (つまり、あなたの場合、削除された行)が出力されます。また、いくつかの diff のような、他のソリューションでは提供されていないオプションがあります。 -i で大文字小文字を無視したり、様々な空白オプション( -E , -b , -v など)を使用すると、より厳密なマッチングが可能になります。

説明

オプション --new-line-format , --old-line-format と --unchanged-line-format を制御することができます。 diff と同様、差分をフォーマットします。 printf フォーマット指定子です。これらのオプションは 新しい (追加)となります。 古い (削除) と 変更なし という行があります。一方を空の ""に設定すると、その種の行が出力されなくなります。

をご存知の方は ユニファイドディフ というフォーマットで部分的に再現することができます。

diff --old-line-format="-%L" --unchanged-line-format=" %L" \
     --new-line-format="+%L" file1 file2

は %L のように、それぞれの行の前に "+" "-" または " " を付けます。 diff -u (差分のみを出力することに注意。 --- +++ と @@ の行を、グループ化された各変更の先頭に追加してください)。 また、これを使って、次のような便利なこともできます。 各行に番号を付ける と %dn .

は diff メソッド（他の提案と一緒に comm と join を使用した場合のみ、期待通りの出力が得られます。 ソート済み を使用することができます。 <(sort ...) を使えば、その場でソートできます。以下は、単純な awk (nawk) スクリプト (Konsoleboxの回答でリンクされているスクリプトに触発された) は、任意の順序で並べられた入力ファイルを受けとります。 と は、足りない行をfile1の中で発生した順に出力します。

# output lines in file1 that are not in file2
BEGIN { FS="" }                         # preserve whitespace
(NR==FNR) { ll1[FNR]=$0; nl1=FNR; }     # file1, index by lineno
(NR!=FNR) { ss2[$0]++; }                # file2, index by string
END {
    for (ll=1; ll<=nl1; ll++) if (!(ll1[ll] in ss2)) print ll1[ll]
}

これは、file1 の全内容を一行ずつ、行番号をインデックス化した配列に格納します。 ll1[] そして，file2 の全内容を行単位でインデックス付けされた連想配列 ss2[] . 両方のファイルを読み込んだら ll1 を使用し in 演算子を使って、file1 の行が file2 に存在するかどうかを判断します（これは diff というメソッドがあります(重複している場合)。

ファイルが十分に大きく、両方を保存するとメモリの問題が発生する場合は、file1のみを保存し、file2の読み込み時に途中でマッチを削除することで、CPUとメモリを交換することができます。

BEGIN { FS="" }
(NR==FNR) {  # file1, index by lineno and string
  ll1[FNR]=$0; ss1[$0]=FNR; nl1=FNR;
}
(NR!=FNR) {  # file2
  if ($0 in ss1) { delete ll1[ss1[$0]]; delete ss1[$0]; }
}
END {
  for (ll=1; ll<=nl1; ll++) if (ll in ll1) print ll1[ll]
}

上記は，file1 の内容全体を，行番号でインデックス付けされた 2 つの配列に格納しています。 ll1[] 行の内容でインデックスされたもの ss1[] . 次に、file2 が読み込まれると、一致する各行が ll1[] と ss1[] . 最後に file1 の残りの行が元の順序を保って出力されます。

この場合、前述のような問題で、さらに 分割統治 GNUを使って split (フィルタリングはGNU拡張)、file1のチャンクで繰り返し実行し、その度にfile2を完全に読み込む。

split -l 20000 --filter='gawk -f linesnotin.awk - file2' < file1

の使用と配置に注意してください。 - 意味 stdin について gawk コマンドラインを使用します。これは split をfile1から1回あたり20000行のチャンクで起動する。

非GNUシステム上のユーザーのために、あなたが入手できるGNU coreutilsパッケージがほぼ確実に存在し、OSXでは アップルXcode ツールで、GNU diff , awk のみですが、POSIX/BSDの split GNUバージョンではなく