2ファイル間で、カンマ区切りの範囲で一致する行を、除外するには

Question

実現したいこと

大元のファイルのカンマ区切りの先頭が、
比較対象のファイル内の行と一致する行を、除外したいです。

▼データのイメージ

大元のファイル：src.txt

10,0
9,0
8,0
7,0
6,0
5,0
4,0
3,0
2,0
1,0

比較対象のファイル：dst.txt

1
2
3
4
5

▼期待される出力結果

src.txtのうち、「5,0」~「1,0」の5行が
除外されたテキストが、出力される。

最終的な出力結果は、ソートされていなくてもOKなものとする。

10,0
6,0
7,0
8,0
9,0

前提

src.txt側が数百万行単位の大規模データとなっても、
実行時間を短縮できるように、なるべくパフォーマンスを重視したいです。

PythonやPHP等のスクリプト言語で、
配列ループ・配列の要素判定をする方式であれば、
比較的容易に実現可能ではありますが、実行速度に難がある状態です。

また、古いシステムでも利用できるように、
可能な限りbashやperl辺りで完結させたいと考えております。

試したこと

commコマンド、cutコマンドを組み合わせるやり方では、
src.txt側に元々入っている付属情報が抜け落ちてしまっています。
（最終的には、,0の部分まで、該当の行全体が出力されるようにしたい）

$ comm -23 <(sort src.txt | cut -f 1 -d ',') <(sort dst.txt)
10
6
7
8
9

補足情報（FW/ツールのバージョンなど）

• CentOS 6.6
• bash 4.1.2
• perl 5.10.1
• Python 2.6.6

Comments

[arcxor]

1 は 10 に部分一致しますがなぜ 10 は残るのでしょうか。部分一致の定義を明確にしてください。

[Mocha]

確かに仰る通りでした。
「部分一致」というよりは、「src.txtをカンマ区切りにした状態の1列目のテキストが、dst.txt側の行に含まれているかどうか？」等の方が適切でした。

Answer 1

パフォーマンスは実行環境にも影響を受けますので、質問者さんの環境で測定してください。

Pythonでも愚直にループを回すのではない方法はあります。集合型を使ってみました。

dst = set()
with open('dst.txt') as f:
    for line in f:
        line = line.strip()
        if len(line):
            dst.add(line)

with open('src.txt') as f:
    for line in f:
        key, _ = line.split(",", 1)
        if key in dst:
            continue
        print(line, end="")

Python 3.x向けです。Python 2.7で使用するには最終行を "print line," に変更します。

Comments

[Mocha]

ご回答いただきありがとうございます。

集合型を使う方法は思いつきませんでした。
確かに集合型で判定すれば、愚直にループさせるよりも早くなりそうですね。

動作想定のシステムでは、まだ2系のPythonが動いているため、
仰る通り調整が必要になりそうです。

[ikedas]

Python 2.7はprint文の書式を変えるだけでした。

ところで、「パフォーマンス」を気にしていらっしゃったのに測定はされないのでしょうか。
私の手元では、src.txtが10000行、dst.txtが1000行の場合、次の結果となりました。

python 2.7:
real 0m0.039s
user 0m0.024s
sys 0m0.015s

grep:
real 0m0.105s
user 0m0.076s
sys 0m0.030s

join:
real 0m0.036s
user 0m0.028s
sys 0m0.014s

Pythonとjoin方式とは遜色ないですが、データが100万行オーダーに増えた場合にどちらが速いかは検証が必要でよう。また、メモリ使用量が問題になる可能性もあります。

再度。パフォーマンスは質問者さんの環境で測定してください。

[Mocha]

追加でコメントいただきありがとうございます。
Python 2系でも、print "string", で改行文字無しで文字列を出力できるのですね。
https://www.lifewithpython.com/2013/12/python-print-without-.html

src.txtを700万件、dst.txtを5万件の状態で、実行時間の計測も含めて、再度テストしてみました。
私の環境ではPython 2.6.6でしたが、それでもPythonが一番早く終了しました。
古いシステムであっても、コマンド以外の方法も含めて柔軟に考えるのが大事ですね。。

▼grepの場合
time grep -Ev -f <(sed -E 's/^.+$/^&,/' dst.txt) src.txt > filtered_list.txt
real 1m34.214s
user 1m28.832s
sys 0m3.059s
※filtered_list.txtが336万件強の時点で、強制終了。（恐らくメモリ不足？）

▼joinの場合
time join -v1 -t, <(sort -t, -k1,1 src.txt) <(sort dst.txt) > filtered_list.txt
real 0m20.384s
user 0m19.427s
sys 0m0.273s

▼Pythonの場合
time python filter.py > filtered_list.txt
real 0m5.685s
user 0m5.423s
sys 0m0.135s

※joinの場合・Pythonの場合の共に、除外後のリストの内容が一致していることも確認できました。
diff <(sort <LIST_BY_JOIN>) <(sort <LIST_BY_PYTHON>)

※そして今更ながら、似たような質問が既に出ておりました・・。申し訳ありません。
https://teratail.com/questions/t6o7mwtp092kg0

[Mocha]

もしPythonも入っていない環境で、同様のことを実現したい場合、
awkコマンドを使うという手もありそうです。
今回のケースでは、Pythonを別途インストールして使うのがベストではありますが。

time awk -F, 'FNR==NR{a[$1]++; next} !a[$1]' dst.txt src.txt > filtered_list.txt
real 0m7.110s
user 0m6.422s
sys 0m0.474s

awkコマンドの場合は、src.txt側の列数が変わっても、同じ内容で動作するというメリットもあるようです。
（試してみて気づきになったので、コメントに残しておきます）

Answer 2

「src.txtをカンマ区切りにした状態の1列目のテキストが、dst.txt側の行に含まれているかどうか？」

grep コマンドの場合

$ grep --version
grep (GNU grep) 3.11

$ grep -Ev -f <(sed -E 's/^.+$/^&,/' dst.txt) src.txt
10,0
9,0
8,0
7,0
6,0

join コマンドの場合

$ join --version
join (GNU coreutils) 9.1

$ join -v1 -t, <(sort -t, -k1,1 src.txt) <(sort dst.txt)
10,0
6,0
7,0
8,0
9,0

Comments

[Mocha]

ご回答いただきありがとうございます。

Linuxコマンドのみで完結されている点、
複数の例を提示してくださっている点から、
ベストアンサーとさせていただきました。

src.txtを700万件、dst.txtを5万件に増やして確認してみました。
grepコマンドの場合は、残り5万件ほどのところで
処理が暫く止まってしまいましたが、
joinコマンドの場合は、ものの数秒で処理が完了しておりました。

いずれのやり方も、発想として全く思い浮かばず、勉強になりました。