4

2 つのファイルの違いをファイ​​ルに書き込むプログラムを作成する必要があります。プログラムは、13.464.448 行を超える 600 MB のファイルをループし、別のファイルで grep が true を返すかどうかを確認し、結果を別のファイルに書き込む必要があります。約 1.000.000 レコードで簡単なテストを作成しましたが、1 時間以上かかったので、このアプローチには 9 時間以上かかる可能性があると推測しています。

これを高速化するための推奨事項はありますか? 使用すべき特定の言語はありますか? 私はbashまたはpythonでそれを行うことを計画していました。

よろしくお願いします。

[編集 1]:申し訳ありませんが、2 つのファイルの違いを言うとき、違いを意味するものではありません。結果ファイルの形式が異なります。

ロジックは次のようになります。

ファイル A には 297,599 行あります ファイル B には 1,300 万行以上あります

ファイル A から読み取られている現在の行を選択し、それをファイル B で grep します。その行がファイル B に存在する場合は、それを結果ファイルに書き込みます。ちなみに、ファイルAとファイルBはフォーマットが異なります。結果ファイルはファイル A の形式になります。

[編集 2]:理想的には bash ソリューションを作成して、これを実行する必要があるすべてのマシンに python をインストールする必要がないように、職場で依頼されました。

これは私の現在の実装です:

#!/bin/bash

LAST_TTP=`ls -ltr TTP_*.txt | tail -1 | awk '{ print $9 }'`
LAST_EXP=`ls -ltr *.SSMT | tail -1 | awk '{ print $9 }'`

while read -r line; do
   MATCH="$(grep $line $LAST_EXP)"
   echo "line: $line, match: $MATCH"

   # if not empty
   if [ ! -z "$MATCH" ]
   then
      echo $MATCH >> result
   fi

done < $LAST_TTP

この bash アプローチは、完了するまでに 10 時間以上かかります。bash でより効率的にする方法について何か提案はありますか?

よろしくお願いします！

4

7 に答える 7

9

セットではなくリストを探している可能性があり、O（n²）のパフォーマンスにつながります。試す：

with open('b') as b:
  blines = set(b)
with open('a') as a:
  with open('result', 'w') as result:
    for line in a:
      if line not in blines:
        result.write(line)

均一に長い（そして過度に長い行ではない）と仮定すると、この実装のパフォーマンスは次のようになります（ Pythonは非常に高速O(|A| + |B|)であるため、償却されます）。メモリ需要はにありますが、係数は1より大幅に大きくなっています。setO(|B|)

出力の行の順序が重要でない場合は、両方のファイルを並べ替えてから、行ごとに比較することもできます。これは、のオーダーのパフォーマンスになりO(|A| log |A| + B log |B|)ます。メモリ需要はO(|A|+|B|)、より正確には|A|+になり|B|ます。

于 2012-05-29T15:07:02.047 に答える
4

各入力ファイルを並べ替えます。次に、それぞれから1行を読み取ります。一方の行がもう一方の行よりも比較が少ない場合は、それを差として出力し、そのファイルから次の行を読み取ります。両方の行が等しい場合は、両方のファイルから次の行を読み取ります。1つのファイルの最後まで読んだ場合、他のファイルのすべての行が異なります。

これは、最初に使用したO（n ^ 2）アルゴリズムとは対照的に、O（n log n）アルゴリズムです。

于 2012-05-29T15:16:44.330 に答える
2

join コマンドも、必要なことを行います。join では、両方のファイルを前もってソートする必要があります。オプション -v は、ペアにできない行ごとに行を出力します。

したがって、次のようなものが必要になります

参加 -v 1 sortedfile1 sortedfile2

(ファイル形式に応じて結合オプションを設定する必要があります。結合のマンページを参照してください)

以下の例では、2 番目の resp を使用してファイル test1.txt と test2.txt を結合します。結合の最初のフィールド。ファイルが sort コマンドを使用して前もってソートされていると仮定します。-v 1 オプションは、test1.txt の行を結合できなかったことのみを出力します。

>cat test1.txt
1 2
b 2 3

> 猫 test2.txt
1×
4×

> 参加 -v 1 -1 2 -2 1 test1.txt test2.txt
2 b 3

> 参加 -v 1 -1 2 -2 1 -o 1.1 1.2 1.3 test1.txt test2.txt
b 2 3

並べ替えと結合は、大きなファイルでも問題なく機能します。

于 2012-05-29T16:28:40.903 に答える
2

grep必要に応じて、最初の一致が見つかったときに を停止することで、スクリプトをわずかに高速化できます。

grepサポートする場合は、 を使用しますgrep -m 1。

あなたの問題は、grepほぼ 300,000 回生成し、毎回 13,000,000 行以上を読み取っていることです。

最初の一致で停止grepすることは少しは役に立ちますが、これらすべての exec のオーバーヘッドも大きな要因です。Python で実装すると、この問題が解消されます。

スクリプト内のファイルの選択については、 BashFAQ/003およびParsinglsを参照してください。

于 2012-05-29T17:44:20.383 に答える
2

あなたの実装は次のようです：

grep --fixed-strings --file=file_B file_A > result_file

しかし、@ phihag と @mark Ronsam の両方の回答がより良い解決策です。

また、ヘビーガンを使用したい場合、ソリューションは Hadoop などの map-reduce フレームワークに適しています。

于 2012-05-29T15:22:10.277 に答える
1

私はcommコマンドを検討します。grep は常に線形検索を実行しますが、並べ替えられたデータで動作するため、grep よりも高速である必要があります。

comm -2 -3 <(sort file1) <(sort file2)
于 2012-05-29T16:32:53.870 に答える
0

awk も使用できます。

awk 'NR==FNR { arrA[$0]; next } $0 in arrA' file_A file_B > result

コマンドラインでのファイル (... file_A file_B) の順序は非常に重要です。

于 2012-05-29T23:57:06.677 に答える