Mitzyuki's Blog

行抜き出しの速度

某所で話題になったのでテキストファイルの行抜き出し速度を検証してみた。
検証用のデータは若干サイズ的に不足があるのだが、 以下のシェル芸で 24M のランダムなテキストデータを作成した。

$ for i in `seq 50000`; do printf "%05d:%s\n" $i `LC_CTYPE=C tr -c -d 'a-zA-Z0-9' < /dev/urandom | dd bs=501 count=1 2> /dev/null`; done > base
$ ls -l base
total 49616
-rw-r--r--  1 mitz  staff  25400000  5 11 12:15 base
    

作業は全て iMac 上で実施した。

$ uname -a
Darwin coredump.local 12.6.0 Darwin Kernel Version 12.6.0: Wed Mar 18 16:23:48 PDT 2015; root:xnu-2050.48.19~1/RELEASE_X86_64 x86_64
    

検証は以下の手段による行の抜き出しの100回繰り返しを10回実行した時の平均た時間を計測した。

• tail(1) と head(1) の組み合わせ (入力ファイルを tail(1) の引数として直接指定)
• tail(1) と head(1) の組み合わせ (入力ファイルを cat(1) を利用してパイプ経由で tail(1) に通知)
• head(1) と tail(1) の組み合わせ (入力ファイルを head(1) の引数として直接指定)
• head(1) と tail(1) の組み合わせ (入力ファイルを cat(1) を利用してパイプ経由で head(1) に通知)
• sed 単体 (入力ファイルを sed(1) の引数として直接指定)
• sed 単体 (入力ファイルを cat(1) を利用してパイプ経由で sed(1) に通知)
• awk 単体 (入力ファイルを awk(1) の引数として直接指定)
• awk 単体 (入力ファイルを cat(1) を利用してパイプ経由で awk(1) に通知)
• sed 単体で検出後即時終了 (入力ファイルを sed(1) の引数として直接指定)
• sed 単体で検出後即時終了 (入力ファイルを cat(1) を利用してパイプ経由で sed(1) に通知)
• awk 単体で検出後即時終了 (入力ファイルを awk(1) の引数として直接指定)
• awk 単体で検出後即時終了 (入力ファイルを cat(1) を利用してパイプ経由で awk(1) に通知)

結果は以下の通り。 自分の予想に反して head(1) と tail(1) の組み合わせが一番早くて驚き。
OS X の標準コマンドなので GNU 拡張された head(1) や tail(1) ではない筈なので、 そもそもオリジナルの head(1) の実装が良いのだろうか。

追記

twitter 及び当ブログのコメントで指摘を頂いたので sed(1) と awk(1) で 行を検出した場合は終了する場合の時間も計測してみました。
head(1) と tail(1) をパイプで繋いだ場合も、 2番目のコマンドで1行出力すると SIGPIPE が発生して 1番目のコマンドも終了しているのだろうか?

tail -n 4036 base | head -1	real 0m0.843s user 0m0.542s sys 0m0.406s
cat base | tail -n 4036 | head -1	real 0m16.681s user 0m16.071s sys 0m1.900s
head -n 4036 base | tail -1	real 0m1.495s user 0m1.571s sys 0m0.351s
cat base | head -n 4036 | tail -1	real 0m1.534s user 0m1.667s sys 0m0.512s
sed -n '4036p' base	real 0m3.183s user 0m2.262s sys 0m0.835s
cat base | sed -n '4036p'	real 0m2.485s user 0m2.240s sys 0m1.253s
awk '{ if(NR==4036) print $0 }' base	real 0m19.430s user 0m18.357s sys 0m0.893s
cat base | awk '{ if(NR==4036) print $0 }'	real 0m18.911s user 0m18.513s sys 0m1.369s
sed -n '4036{p;q;}' base	real 0m0.467s user 0m0.270s sys 0m0.182s
cat base | sed -n '4036{p;q;}'	real 0m0.456s user 0m0.347s sys 0m0.353s
awk '{ if(NR==4036){ print $0; exit;} }' base	real 0m1.852s user 0m1.581s sys 0m0.199s
cat base | awk '{ if(NR==4036){ print $0; exit;} }'	real 0m1.775s user 0m1.676s sys 0m0.355s