grepはどのように速く動作しますか？

Question

私は本当にシェルのGREPの機能に驚いています。以前はjavaでsubstringメソッドを使用していましたが、今はGREPを使用しています。これは数秒で実行されます。私の経験によれば、私は間違っているかもしれません。

私はそれがどう起こっているのか理解できていないと言われていますか？ウェブ上ではあまり利用できません。

誰もがこれを手伝ってくれますか？

Answer 1

具体的にはGNU grepとお考えください。著者：Mike Haertelからの注釈は次のとおりです。

GNU grepはすべての入力バイトを見逃すため、高速です。それは で見ていEACH BYTEのために非常に少数の命令を実行するので

のGNU grepが速いです。

のGNU grepが対象文字列の最後の文字のための最初の に見える有名ボイヤー - ムーアのアルゴリズムを使用して、 にルックアップテーブルを使用して、それが見つかった時はいつでも、それは入力にスキップすることができますどのくらい先にそれを伝えますa 文字が一致しません。

のGNU grepのもボイヤー - ムーアの内部ループをアンロールし、それがすべてのアンロールステップでループ終了テストを行う する必要がないように ボイヤー - ムーアデルタテーブルエントリを設定します。その結果、 という制限で、GNU grepは実際に見ている入力バイトごとに3つ以下のx86命令 が実行されています（そして、それは多くの場合 バイトをスキップします）。

GNU grepは未処理のUnix入力システムコールを使用し、読み取った後にデータ のコピーを避けます。さらに、GNU grepは入力を LINESに侵害しないようにします。改行を検索すると、毎回 を見なければならない改行を見つけるために、 の倍数でgrepを遅くするでしょう！だからではなく、行指向の入力を使用しての

は、GNUのgrepが、 に大きなバッファを生データを読み込むボイヤー - ムーアを使用してバッファを検索し、それが検出された場合にのみ を試合はそれが行くとバウンディング改行 探しありません（ のようないくつかのコマンドラインオプションは、この最適化を無効に-n。）

この答えはhereから取られた情報のサブセットです。

Answer 2

スティーブの優れた答えに追加します。

それは広く知られているが、より長いパターンで、ボイヤー - ムーアスキップすることができますので、grepが、ほとんど常にを速く短いものより長いパターン文字列をgrepをするときであることはできません前方の長い進歩でより良い達成するためにサブリニア速度：

例：

# after running these twice to ensure apples-to-apples comparison 
# (everything is in the buffer cache) 

$ time grep -c 'tg=f_c' 20140910.log 
28 
0.168u 0.068s 0:00.26 

$ time grep -c ' /cc/merchant.json tg=f_c' 20140910.log 
28 
0.100u 0.056s 0:00.17 

長いフォームは35％高速です！

どうしてですか？ Boyer-Mooreは、パターン・ストリングからスキップ・フォワード・テーブルを導出し、不一致があれば、入力内の単一の文字をスキップ内のcharと比較する前に、可能な限り長いスキップを（最後の文字から最初に）表。

はここa good video explaining Boyer Moore

（GNUのgrepのための）他の一般的な誤解だfgrepがgrepよりも高速であるということです。 fのfgrepは 'fast'の略ではなく、 'fixed'（マニュアルページを参照）の略で、両方とも同じプログラムであり、両方ともBoyer-Mooreを使用しているため、 regexp特殊文字を使用せずに固定文字列を検索します。私がfgrepを使用する唯一の理由は、正規表現の特殊文字（.、[]、または*など）がある場合です。このように解釈されることは望ましくありません。そして、その場合でさえ、grep -Fのより移植性の高い/標準的な形態が、fgrepよりも好ましい。