lookコマンドによる二分探索が速すぎて見えない
Linuxコマンドブック ビギナーズ 第2版 コマンドブックシリーズ
- 作者: 田谷文彦,三澤明
- 出版社/メーカー: ソフトバンク クリエイティブ
- 発売日: 2007/04/11
- メディア: 単行本
- クリック: 3回
- この商品を含むブログ (2件) を見る
grep vs look
数GByte容量の圧縮ファイルから特定の文字列を検索したい場合があります。一度きりのgrep検索処理であればそれほど気にする事はありませんが、System処理で何度も検索をするようなケースでは処理に時間がかかってしまいます。今日はsortされたファイルに対してlookという2分探索コマンドを利用するとgrepより高速に検索が可能ということを調べたいと思います。
lookコマンドの活用
lookは通常の場合辞書ファイルからスペルを確認するために利用されます。例えばmorpholoと先頭一致する単語一覧を取得したい場合は$ look morpholoと実行します。単語一覧の辞書データは/usr/share/dict/wordsに配置されています。
$ look morpholo morphologic morphological morphologically morphologies morphologist morphologists morphology morpholoical辞書ファイルを見るとわかりますがlookを使うには予めデータをsortしておく必要があります。これはlookの内部処理で2分探索を行っているためだと思われます。lookは上の辞書だけでなくgrepと同じように引数に指定したファイルから検索を行う事ができます。lookのusageは以下のようになっています。
look 使い方: look [-dfa] [-t キャラクタ] 文字列 [ファイル]
圧縮ファイルへの検索
検索手段
圧縮ファイルに対する文字列検索の手段で思い当たるものは以下のものです。以下のそれぞれを検証して行きます。
検索対象ファイル作成
手元に手頃なgzファイルが無かったので16進数の文字列を改行で出力するスクリプトで作成します。以下のスクリプトで生成されるログファイルは5.7GByte、gz圧縮ファイルで2.9GByteとなっています。
#!/usr/local/bin/perl use strict; use warnings; open( OUT, "> ./log.txt" ); for( my $i=0; $i<100000000; $i++ ) { my @arr = (); for( my $j=0; $j<30; $j++ ) { push @arr, int( rand(100) ); } print OUT unpack( "H*", pack("C*", @arr ) ) . "\n"; } system( "gzip ./log.txt" );zgrepで検索
zgrepという圧縮ファイル用のgrepコマンドで検索を行います。-Fオプションは正規表現を使わない代わりに高速に検索できます。
実行した結果処理時間は1:43.23となりました。$ zgrep -F "282033131e1d4b59034b17040d4f51440a2e014c594e571f270f0f453357" log.txt.gz 26.03s user 67.30s system 90% cpu 1:43.23 totalzcatで出力 + grepで検索
ファイルを解凍せずにzcatで圧縮ファイルの中身を出力してからパイプでgrepを行います。zgrepと同じく-Fオプションで高速に検索させます。(fast grepと呼ぶらしいです。)
実行した結果処理時間は1:52.54となりました。$ time zcat log.txt.gz | grep -F "282033131e1d4b59034b17040d4f51440a2e014c594e571f270f0f453357" zcat log.txt.gz 22.29s user 59.77s system 72% cpu 1:52.54 total grep -F "282033131e1d4b59034b17040d4f51440a2e014c594e571f270f0f453357" 2.27s user 9.53s system 10% cpu 1:52.54 totalファイル解凍 + grepで検索
ファイルを解凍した後からの処理時間を計測します。
実行した結果処理時間は1:01.72となりました。$ time gunzip log.txt.gz 35.75s user 43.67s system 43% cpu 3:03.25 total $ time grep -F "282033131e1d4b59034b17040d4f51440a2e014c594e571f270f0f453357" log.txt 0.15s user 10.42s system 17% cpu 1:01.72 totalファイル解凍 + sort + lookで検索
ファイルを解凍した後にsortを行ってデータを昇順に並び替えます。その後にlookコマンドで検索を行います。
実行した結果処理時間は0.036となりました。速い、速すぎるぞ、lookコマンド〜〜!!$ time sort log.txt > sort_log.txt 483.14s user 158.01s system 50% cpu 21:01.04 total $ time look "282033131e1d4b59034b17040d4f51440a2e014c594e571f270f0f453357" sort_log.txt 0.00s user 0.01s system 33% cpu 0.036 total
比較まとめ
- 検索処理速度という意味ではlookコマンドが圧倒的な力を見せつけてくれました。2分探索恐るべしという結果です。
- grepは逐次検索なのでファイルの先頭から最後までが検索対象となってしまいます。2分探索は一部だけを検索していると思います。
- lookコマンドはgrepのように豊富なオプションは存在しません。1ファイルに対してのみ検索を行う事ができるコマンドです。
- lookコマンドを使うためにはzgrepのように圧縮ファイルに対して直接コマンドを実行する事ができないので解凍が必要になります。また事前にデータをsortしておく必要もありますが、何度もファイルに対して検索を行うような場合はsort + lookを使うようにすると良いと思います。
- 以下は比較表です。圧縮ファイルサイズ2.9G、解凍ファイル5.7Gの文字列に対する検索機能という観点で比較を行っています。
検索機能 処理時間 zgrep 1m43.23s zcat + grep 1m52.54s 解凍 + grep 1m01.72s 解凍 + sort + look 0.036s