あるファイルの行を別のファイルの行と一致させます。

あるファイルの行を別のファイルの行と一致させます。

私はかなり大きなリスト(100万個)ともう1つの大きなリスト(17GB)を持っています。

リスト1:

98433259@34
90345394@43
94335053@23

リスト2

54353456@35:nancy
98433259@34:jack
94335053@23:james
32409533@86:robert

出力:

98433259@34:jack
94335053@23:james

grep -Fwf list1 list2を試しましたが、遅すぎました。

これを行うより速い方法がありますか?

答え1

遅すぎる?何が期待できますか?ファイルサイズを12MBとすると、約100万行になります。これで、別のファイルの各行に対してファイル全体をスキャンする必要があります。 10番のうち9番は比較が最初のバイトの後に停止されると主張することができますが、それでも次の改行文字を引き続き検索する必要があるため、実際には2番目のファイルのすべての行に対して最初のファイルのすべてのバイトが渡されます。 CPU。

2番目のファイルには10億行があります。したがって、12MBを10億回スキャンする必要がありますが、これは12エクサバイトです!デスクトップに8MBのL3キャッシュがある場合、その12MBは合わず、RAMからインポートする必要があります。幸いなことに、最近はRAMの速度が速く、コンピュータの有効スループットが20GB / sになる可能性があります。正しく計算すると、20GB / sで12 Exebyteにアクセスするのに600.000秒かかります。 10,000分。 167時間。 7日。一週間。

ところで、遅くはなく、本当に速いです!とても難しい作業なので時間がかかります。

迅速に進むには、その目的に合わせて設計されたツールが必要です。うまくいかないので、自分で書いてください。

どのように?と同じクイック言語を使用してCfile1データを最初にクリーンアップすると、すべてのデータをスキャンする必要はありません。各レコードをツリーに入れます。ルートには、最初の数字に従ってサブツリーへの10個のポインタがあります。ヌルポインタが葉がないことを示さない限り、各サブツリーにはサブツリーへの10個の追加ポインタがあります。

これで、file2をスキャンするときに最初のバイトを取得し、その数値に基づいてポインタを取得し、そのサブツリーから2番目の数字へのポインタを選択するなどの操作を実行します。 8ビットの数字と64ビットのポインタを使用して、最悪の場合(一致するものを見つける)、64バイトと名前に格納されているバイトのみをロードします。 1行に80バイト、10億回すると80GBになり、4秒でメモリから取り出されます。もっといいと思いますか?

これはより速い方法ですが、UNIXとは何の関係もありません。このようなプログラムを書く方法がわからない場合は、StackOverflowに尋ねてください。ここを参照してください。

関連情報