124

シェルでのGREPの機能には本当に驚いています。以前は、Javaで部分文字列メソッドを使用していましたが、現在はGREPを使用しており、数秒で実行されます。これは、以前作成したJavaコードよりもはるかに高速です。 （私の経験によると、私は間違っているかもしれませんが）

そうは言っても、私はそれがどのように起こっているのか理解できていませんか？また、Web上で利用できるものはあまりありません。

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

4

2 に答える 2

188

あなたの質問がGNU grep具体的に関係していると仮定します。著者のMikeHaertelからのメモは次のとおりです。

GNU grepは、すべての入力バイトを探すことを回避するため、高速です。

GNU grepは、それ が見るバイトごとに非常に少数の命令を実行するため、高速です。

GNU grepは、よく知られているボイヤームーアアルゴリズムを使用します。このアルゴリズムは、最初にターゲット文字列の最後の文字を検索し、ルックアップテーブルを使用して、一致しない文字が見つかったときに入力をスキップできる距離を通知します。

GNU grepはまた、ボイヤー-ムーアの内部ループを展開し、展開されたすべてのステップでループ終了テストを実行する必要がないように、ボイヤー-ムーアデルタテーブルエントリを設定します。この結果、制限内で、GNU grepは、実際に参照する入力バイトごとに実行されるx86命令の平均が3未満になります（そして、多くのバイトを完全にスキップします）。

GNU grepは、生のUnix入力システムコールを使用し、データの読み取り後にデータをコピーすることを回避します。さらに、GNU grepは、入力を行に分割することを回避します。改行を探すとgrepが数倍遅くなります。改行を見つけるには、すべてのバイトを調べる必要があるからです。

したがって、行指向の入力を使用する代わりに、GNU grepは生データを大きなバッファーに読み込み、Boyer-Mooreを使用してバッファーを検索し、一致するものが見つかった場合にのみ、境界の改行を探します（-のような特定のコマンドラインオプションnこの最適化を無効にします。）

この回答は、ここから取得した情報のサブセットです。

于 2012-09-27T21:56:54.700 に答える
47

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

広く知られていないかもしれませんが、長いパターンでは、ボイヤームーア文字がより長いストライドで前方にスキップしてさらに優れたサブリニア速度を実現できるため、短いパターン文字列よりも長いパターン文字列を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は、パターン文字列からスキップフォワードテーブルを作成し、不一致がある場合は常に、入力の1つの文字をスキップテーブルの文字と比較する前に、可能な限り長いスキップ（最後の文字から最初の文字まで）を選択します。

これがボイヤームーアを説明するビデオです（ kommradHomer へのクレジット）

（GNU grepの）もう1つの一般的な誤解は、fgrepよりも速いということですgrep。finfgrepは「fast」を表すのではなく、「fixed」を表します（manページを参照）。どちらも同じプログラムであり、どちらもBoyer-Mooreを使用しているため、fixed-を検索するときに速度に違いはありません。正規表現の特殊文字を含まない文字列。私が使用する唯一の理由fgrepは、正規表現の特殊文字（、、、.など[]）*がある場合です。そのように解釈されたくない場合です。そしてそれでも、よりポータブルで標準的な形式grep -Fが優先されfgrepます。

于 2014-09-10T05:36:27.293 に答える