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フォーマットを調整するために使用されます。
これは入力サイズに応じて線形時間で実行する必要があります。
答え2
このメソッドは次のように使用します。固定長さキーはレコードの最初のバイトから始まります。
一時フィールド区切り文字（または一意のシングルバイト文字）を使用すると、\x01レコードをより簡単に操作できます。
join -t$'\x01' <(sed -r 's/.{9}/&\x01/' main) <(cut -b -9 keys) |sed -r 's/(.{9})./\1/'
マックスシュレプチガー awkこの例は、45,000,000レコードの場合は高速ですが、より大きなファイルの場合は失敗します。空きメモリーはどれくらいありますか？
結果は次のとおりです。
45,000,000 unique records, 1,500,000 keys
=========================
awk
real 0m31.971s
user 0m28.782s
sys 0m2.972s
join
real 0m53.733s
user 0m54.255s
sys 0m0.708s
(2x45) 90,000,000 records, 1,500,000 keys
=========================
awk
awk: (FILENAME=main2 FNR=54334297) fatal: assoc_lookup: bucket->ahname_str: can't allocate 11 bytes of memory (Cannot allocate memory)
join
real 1m35.306s
user 1m34.754s
sys 0m1.344s
===================
答え3
ラインベースのファイルであると仮定すると、grepかなりうまく機能します。固定文字列-f keyfileに合計を使用してください。-F
grep -F -f keys textfile
注：以下のコメントの誤検出に関するPeterOの警告を参照してください。