42M行のテキストファイルがあります。各行の最初の9文字は数字キーです。約150万のキーリストにキーが存在する行だけを抽出する最も効率的な方法は何ですか？ファイルとキーのリストの両方がソートされます。
ベストアンサー1
使用するのに十分効率的でなければなりませんawk。キールックアップ時間がキー数（照会テーブルの数（例では比較的小さい））に基づいて代数的に拡張される組み込み連想配列を提供します。
あなたのコメントは次のとおりです。
42M * log2(1.5M) -> 42M * 20 key comparisons
（ここでMは10^6を表します）
awkがハッシュテーブルを使用している場合、各キールックアップには固定時間しかかかりません。
効率的なawkベースのソリューションの例（デフォルトフィールド区切り文字を使用）：
$ awk 'ARGIND == 1 { a[$1] = 1; next } a[$1] { print $0 }' keys.dat largefile.dat
両方の入力がソートされているため、より効率的なスクリプトを作成できます（ランタイムは両方の入力ファイルのサイズに応じて線形に拡張されます）。しかし、プログラミングには時間がかかります。
または、入力としてソートが必要なファイルを使用できますjoin。制限は、キーをアルファベット順に並べる必要があることです。出力フォーマットを調整する必要があるかもしれません。たとえば、
$ join -j1 keys.dat largefile.dat
-tフィールド区切り文字を設定し、出力-oフォーマットを調整するために使用されます。
これは入力サイズに応じて線形時間で実行する必要があります。