[解決済み] どうしてgrepはそんなに速く動くのですか？

質問

以前はJavaのsubstringメソッドを使っていましたが、今はGREPを使って数秒で実行され、以前書いたJavaのコードよりも驚くほど速いです。

とはいえ、どうしてそうなっているのかがわからないのですが、ウェブ上でもあまり公開されていないようです。

どなたか助けていただけませんか？

どのように解決するのですか？

あなたの質問が GNU grep 具体的には 以下は作者 Mike Haertel からのメモです。

GNU grepが速いのは、入力バイトのすべてを見ることを避けるためです。

GNU grepが高速なのは、入力された各バイトに対してごくわずかな命令しか実行しないからです。 入力された各バイトに対して するためです。 を見ることができます。

GNU grepはよく知られたBoyer-Mooreアルゴリズムを使用しています。 を探し、ルックアップテーブルを使い ルックアップテーブルを使用して、マッチしない文字を見つけるたびに、入力のどの程度先まで読み飛ばすことができるかを教えてくれます。 ルックアップテーブルを使用して、一致しない文字が見つかったときに、入力のどの程度先までスキップできるかを知らせます。

GNU grep はまた、Boyer-Moore の内部ループを展開し、Boyer-Moore の差分テーブルのエントリをセットアップします。 Boyer-Moore デルタテーブルのエントリを設定します。 ループの終了テストを行う必要がないように設定します。 この結果 GNU grepが実際に実行する入力バイトごとのx86命令数は平均して3つ以下です。 その結果、GNU grepは実際に見る各入力バイトに対して実行されるx86命令の平均が3以下となります（そして多くのバイトを完全にスキップします）。 バイトを完全にスキップします)。

GNU grep は生の Unix 入力システムコールを使用し、読み込んだ後のデータのコピーを回避します。 しません。さらに、GNU grepは入力を行単位に分割することを避けています。 行に分割することを避けます。 改行を探すと grep の速度が数倍遅くなります。 なぜなら、改行を見つけるためには、すべてのバイトを見なければならないからです。 なぜなら、改行を見つけるために、すべてのバイトを見なければならないからです!

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

この回答は、以下の情報のサブセットです。 ここで .