Y's note

Web技術・プロダクトマネジメント・そして経営について

本ブログの更新を停止しており、今後は下記Noteに記載していきます。
https://note.com/yutakikuchi/

lookコマンドによる二分探索が速すぎて見えない

Linuxコマンドブック ビギナーズ 第2版 コマンドブックシリーズ

Linuxコマンドブック ビギナーズ 第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 キャラクタ] 文字列 [ファイル]

圧縮ファイルへの検索

検索手段

圧縮ファイルに対する文字列検索の手段で思い当たるものは以下のものです。以下のそれぞれを検証して行きます。

  • zgrepで検索
  • zcatで出力 + grepで検索
  • ファイル解凍 + grepで検索
  • ファイル解凍 + sort + lookで検索
検索対象ファイル作成

手元に手頃な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 total
zcatで出力 + 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