2016/05/11

行抜き出しの速度

某所で話題になったのでテキストファイルの行抜き出し速度を検証してみた。
検証用のデータは若干サイズ的に不足があるのだが、 以下のシェル芸で 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
real0m0.843s
user0m0.542s
sys0m0.406s
cat base | tail -n 4036 | head -1
real0m16.681s
user0m16.071s
sys0m1.900s
head -n 4036 base | tail -1
real0m1.495s
user0m1.571s
sys0m0.351s
cat base | head -n 4036 | tail -1
real0m1.534s
user0m1.667s
sys0m0.512s
sed -n '4036p' base
real0m3.183s
user0m2.262s
sys0m0.835s
cat base | sed -n '4036p'
real0m2.485s
user0m2.240s
sys0m1.253s
awk '{ if(NR==4036) print $0 }' base
real0m19.430s
user0m18.357s
sys0m0.893s
cat base | awk '{ if(NR==4036) print $0 }'
real0m18.911s
user0m18.513s
sys0m1.369s
sed -n '4036{p;q;}' base
real0m0.467s
user0m0.270s
sys0m0.182s
cat base | sed -n '4036{p;q;}'
real0m0.456s
user0m0.347s
sys0m0.353s
awk '{ if(NR==4036){ print $0; exit;} }' base
real0m1.852s
user0m1.581s
sys0m0.199s
cat base | awk '{ if(NR==4036){ print $0; exit;} }'
real0m1.775s
user0m1.676s
sys0m0.355s

sed なのですけれども、sed -n '4036p' ... だとファイルを最後までスキャンする事になりますので、

$ sed -n '4036{p;q;}' ...

として計測する方が公平ではないかと。これは awk でも同じです。

$ awk 'NR==4096{print;exit;}' ...

Posted by pitman at 2016/05/11 (Wed) 13:27:00

sed なのですけれども、sed -n '4036p' ... だとファイルを最後までスキャンする事になりますので、

$ sed -n '4036{p;q;}' ...

として計測する方が公平ではないかと。これは awk でも同じです。

$ awk 'NR==4096{print;exit;}' ...

Posted by pitman at 2016/05/11 (Wed) 13:27:42
トラックバック
https://blog.bsdhack.org/index.cgi/Computer/20160511.trackback
コメント














メッセージ: Ready to post a comment.