別のファイルに保存されている行番号に基づいて大容量ファイルから行を抽出する簡単な方法

別のファイルに保存されている行番号に基づいて大容量ファイルから行を抽出する簡単な方法

800億行を含む大容量ファイルがあります。今、いくつかの行(約10000行)を抽出したいと思います。行番号を知っていて、これを処理する最速の方法は何ですか?

この行を抽出するために、行番号を含む他のファイルを使用できますか?行番号ファイルの行番号が常に連続するわけではありません。

たとえば、ソースファイルは次のようになります。

0.1
0.2
0.3
0.4
...

行番号ファイル:

1
3
4

出力:

0.1
0.3
0.4

答え1

以下はそれ以外の選択肢といくつかのベンチマークです。Zhou Weijunの回答から

join

data行を抽出するファイルと抽出する行数をリストするファイルがあるとし、line_numbers出力のソート順序が重要でない場合は、次のようにします。

join <(sort padded_line_numbers) <(nl -w 12 -n rz data) | cut -d ' ' -f 2-

これにより、ファイルの行に番号が付けられ、最初のフィールドdatapadded_line_numbersデフォルト)のファイルと結合され、共通の行が印刷されます(切り捨てられた結合フィールド自体を除く)。

join入力ファイルはアルファベット順にソートする必要があります。上記のファイルは、ファイルの各行をpadded_line_numbers左に記入して準備する必要があります。line_numbersたとえば、

while read rownum; do
    printf '%.12d\n' "$rownum"
done <line_numbers >padded_line_numbers

オプション-w 12 -n rzと引数は、nl前にゼロが付いた12桁の長い数字の出力を指示します。

出力のソート順序がline_numbersファイルのソート順序と一致する必要がある場合は、以下を使用できます。

join -1 2 -2 1 <(nl padded_line_numbers | sort -k 2,2) \
    <(nl -w 12 -n rz data) |
    sort -k 2,2n |
    cut -d ' ' -f 3-

padded_line_numbersファイルに番号を付け、結果を2番目のフィールドに基づいてアルファベット順に並べ替え、番号付きファイルに関連付け、結果を元の並べ替え順dataに番号順に並べ替えますpadded_line_numbers

ここでは、便宜上、プロセス置換を使用します。これに依存できない、または依存したくなく、中間結果を保持するために通常のファイルを作成するために必要なストレージスペースを無駄にする意図がない場合は、名前付きパイプを利用できます。

mkfifo padded_line_numbers
mkfifo numbered_data

while read rownum; do
    printf '%.12d\n' "$rownum"
done <line_numbers | nl | sort -k 2,2 >padded_line_numbers &

nl -w 12 -n rz data >numbered_data &

join -1 2 -2 1 padded_line_numbers numbered_data | sort -k 2,2n | cut -d ' ' -f 3-

ベンチマーク

問題の特異性はファイルの行数なので、data適切な量のデータで代替をテストするのが役に立つと思いました。

テストでは、32億行のデータファイルを使用しました。各行は、およびopenssl encを使用して16進数でエンコードされた2バイトのゴミであり、od -An -tx1 -w2以下を使用してスペースを削除しましたtr -d ' '

$ head -n 3 data
c15d
061d
5787

$ wc -l data
3221254963 data

このファイルは、GNU Coreutilsを使用して1から3,221,254,963までの10,000の数字を繰り返し無作為に選択することによってline_numbers作成されました。shuf

shuf -i 1-"$(wc -l <data)" -n 10000 >line_numbers

bashテスト環境は、i7-2670QM Intelクアッドコアプロセッサ、16GiBメモリ、SSDストレージ、GNU / Linux、5.0、およびGNUツールを備えたノートブックです。
私が測定した唯一の次元は、timeシェル組み込み関数による実行時間でした。

私がここで考えているのは次のとおりです。

perl一番早いようです。

$ time perl_script line_numbers data | wc -l
10000

real    14m51.597s
user    14m41.878s
sys     0m9.299s

awkパフォーマンスはかなりよさそうだ。

$ time awk 'FNR==NR { seen[$0]++ }; FNR!=NR && FNR in seen' line_numbers data | wc -l
10000

real    29m3.808s
user    28m52.616s
sys     0m10.709s

join、また同様のようです。

$ time join <(sort padded_line_numbers) <(nl -w 12 -n rz data) | wc -l
10000

real    28m24.053s
user    27m52.857s
sys     0m28.958s

上記の順序付けられたバージョンは、このバージョンと比較してパフォーマンスの低下がほとんどないことに注意してください。

最後に目立つようにsed遅くなったようでした。約9時間後に終了しました。

$ time sed -nf <(sed 's/$/p/' line_numbers) data | wc -l
^C

real    551m12.747s
user    550m53.390s
sys     0m15.624s

答え2

これにはPerlスクリプトを使用します。私はこれを思い出しました:

#!/usr/bin/perl

# usage: thisscript linenumberslist.txt contentsfile

unless (open(IN, $ARGV[0])) {
        die "Can't open list of line numbers file '$ARGV[0]'\n";
}
my %linenumbers = ();
while (<IN>) {
        chomp;
        $linenumbers{$_} = 1;
}

unless (open(IN, $ARGV[1])) {
        die "Can't open contents file '$ARGV[1]'\n";
}
$. = 0;
while (<IN>) {
        print if defined $linenumbers{$.};
}

exit;

まず、関心のある行番号のリストを連想配列として読みます。ここで行番号はキーです。chomp行末、$_つまり行自体から改行文字を削除します。

次に、データファイルが開き、行番号が行番号配列の既存のキーである場合、行が印刷されます。

これは$.Perlのライン番号カウンタで、ラインを読むたびにインクリメントされます。これはファイル全体で計算されるため、データファイルの行を読み取る前にこれをゼロにリセットしました。

これはおそらく「perl」スタイルでもっと書くことができますが、私はより読みやすくすることを好みます。

抽出する行のリストが非常に大きい場合、これは最も効率的な方法ではないかもしれませんが、Perlは通常これらの操作に非常に効率的であることがわかりました。

リストされた順序で(つまり、順序ではなく)行を抽出する必要がある場合は、より複雑になります。

答え3

ライナーの場合は、以下を使用してくださいsed

sed -nf <(sed 's/$/p/' linenumberfile) contentfile

元の順序を維持するにはlinenumberfile:

sed -nf <(sed 's/$/p/' linenumberfile) contentfile | paste <(nl linenumberfile | sort -n -k 2,2) - | sort -n -k 1,1 | cut -f 3-

説明する:

sed 's/$/p/' linenumberfile

sed指定された行を印刷するスクリプトを生成します。次に、スクリプトは、実際の印刷を実行するためにsed-nパターン空間の基本印刷を抑制するために)他のスクリプトに供給される。コンテンツファイルは1行ずつ処理されるため、sed出力順序はコンテンツファイルと同じです。これはワンパスプロセスだから、速度が許容できることを願っています。

プロセスを高速化するためにこれを変更し、生成されたpスクリプトの最後に{p;b}追加できます。qsed

行番号ファイルの行順序を維持するには、nl「行番号」を使用して行番号ファイルに追加します。だから行番号ファイル

4
5
2

なります

1 4
2 5
3 2

最初の列はファイルの元の行番号の順序を記録します。

次に、「行番号」を含むファイルsortedとpastedをに出力しますsed

3 2    content_of_line2
1 4    content_of_line4
2 5    content_of_line5

次に、sort最初の列をedを実行するキーとして使用し、最後に

1 4    content_of_line4
2 5    content_of_line5
3 2    content_of_line2

最後に、cut2つの追加の列を削除するために使用されました。

ベンチマーク

sedいくつかの行で最もうまくいくようですが、これはperl質問で指定された10000行のアプローチです。

$ cat /proc/cpuinfo | grep -A 4 -m 1 processor
processor   : 0
vendor_id   : GenuineIntel
cpu family  : 6
model       : 60
model name  : Intel(R) Core(TM) i5-4590 CPU @ 3.30GHz

$ wc -l linenumber
10 linenumber

$ wc -l content
8982457 content

$ file content
content: ASCII text

$ time bash -c "sed -nf <(sed 's/$/p/' linenumber) content > /dev/null"    
real    0m0.791s
user    0m0.661s
sys     0m0.133s

$ time bash -c "awk 'FNR==NR { seen[$0]++ }; FNR!=NR && FNR in seen' linenumber content > /dev/null"
real    0m3.061s
user    0m2.908s
sys     0m0.152s

$ time bash -c "./ln.pl linenumber content > /dev/null"
real    0m1.706s
user    0m1.582s
sys     0m0.124s

$ ./genlinenumber.py 100 > linenumber
$ wc -l linenumber
100 linenumber

$ time bash -c "sed -nf <(sed 's/$/p/' linenumber) content > /dev/null"
real    0m3.326s
user    0m3.164s
sys     0m0.164s

$ time bash -c "awk 'FNR==NR { seen[$0]++ }; FNR!=NR && FNR in seen' linenumber content > /dev/null"
real    0m3.055s
user    0m2.890s
sys     0m0.164s

$ time bash -c "./ln.pl linenumber content > /dev/null"
real    0m1.769s
user    0m1.604s
sys     0m0.165s

行の順序を維持する必要がある場合は、|時間が無視されるほど最初の行の後にコマンドを使用できます。

$ ./genlinenumber.py 10000 > linenumber
$ wc -l linenumber
10000 linenumber

$ time bash -c "./ln.pl linenumber content > extract"
real    0m1.933s
user    0m1.791s
sys     0m0.141s

$ time bash -c "paste <(nl linenumber | sort -n -k 2,2) extract | sort -n -k 1,1 | cut -f 3- > /dev/null"
real    0m0.018s
user    0m0.012s
sys     0m0.005s

答え4

micha@linux-micha: /tmp
$ cat numbers.txt
1
2
4
5

micha@linux-micha: /tmp
$ cat sentences.txt
alpha
bravo
charlie
delta
echo
foxtrott

micha@linux-micha: /tmp
$ awk 'FNR==NR { seen[$0]++ }; FNR!=NR && FNR in seen' numbers.txt sentences.txt
alpha
bravo
delta
echo

関連情報