Libx GNU grep 利用ガイド

    このページの内容

    5 性能

    通常、grepはテキストを効率よく検索できます。ただし、状況によってはかなり遅くなることがあります。また、大きなファイルを検索する場合には、わずかな性能調整でも大きな効果が得られることがあります。grepが使用するアルゴリズムは実装の詳細であり、リリースごとに変わる可能性がありますが、基本的な長所と短所を理解すると性能を改善するのに役立ちます。

    grepコマンドの処理の一部は、効率を重視して設計されたオートマトンの組によって行われます。残りは、後方参照のような特殊な機能に高速な照合器が遭遇した場合に処理を引き継ぐ、低速な照合器によって行われます。可能な場合、単一の固定パターンの照合には高速な文字列検索アルゴリズムのBoyer–Moore法を、複数の固定パターンの照合にはAho–Corasick法を使用します。

    一般に、grepは単一バイトのロケールでより効率よく動作します。複数バイト文字に必要な特別な処理を避けられるためです。その条件でもパターンが同じように機能するなら、LC_ALLを単一バイトのロケールに設定すると性能が大きく向上することがあります。grepはCロケールに合わせて調整されているため、特に「LC_ALL='C'」という設定が効率的な場合があります。

    「C」以外のロケールでは、大文字・小文字を区別しない検索や、「[a-z]」「[[=a=]b]」のような角括弧式の検索が、驚くほど非効率になることがあります。複数文字からなる照合要素などの概念へ、高速かつ移植可能な方法でアクセスすることが難しいためです。

    区間指定式は、内部では繰り返しによって実装される場合があります。たとえば、「^(a|bc){2,4}$」は「^(a|bc)(a|bc)((a|bc)(a|bc)?)?$」として実装されるかもしれません。繰り返し回数が大きいと、メモリーを使い切ったり、照合が大幅に遅くなったりすることがあります。回数が小さくても、繰り返しを連ねると問題が起こる場合があります。たとえば、「grep -E ".*{10,}{10,}{10,}{10,}{10,}"」はスタックをあふれさせる可能性が高いものです。幸い、このような正規表現は一般に作為的なものであり、繰り返しを連ねる書き方はPOSIXに適合しないため、いずれにせよ移植可能なプログラムでは使えません。

    「\1」のような後方参照は、場合によって性能を大きく損ないます。一般に、後方参照は有限状態オートマトンでは実装できず、代わりに非常に非効率になることがあるバックトラッキングのアルゴリズムを動作させるためです。たとえば、パターン「^(.*)\1{14}(.*)\2{13}$」は、非負整数xとyについて、長さを和15x + 14yで表せる行だけに一致します。しかし、パターン照合器は線形ディオファントス方程式の解析を行わず、一致する可能性のあるすべての文字列をバックトラッキングで調べます。このアルゴリズムの計算量は、最悪の場合には指数的になります。

    穴のあるファイル、つまり二次記憶装置には物理的に存在しない大きなゼロ領域を持つファイルをサポートする一部のオペレーティングシステムでは、grepはゼロを読み込まずに穴を効率よく飛ばせます。-a（--binary-files=text）オプションを使う場合（ファイルとディレクトリの選択を参照）、この最適化は利用できません。ただし、-z（--null-data）オプションも併用する場合は例外です（その他のオプションを参照）。

    効率のため、grepは必ずしも入力を最後まで読み込みません。たとえば、シェルコマンド「sed '/^...$/d' | grep -q X」では、grepが「X」を含む行を読んだ直後に、残りの入力データを読まずに終了することがあります。その結果、grepが終了した後にはsedが出力パイプへ書き込めなくなるため、sedがゼロ以外の終了ステータスで終了する場合があります。

    grepが使うアルゴリズムと、関連する文字列照合アルゴリズムについて詳しくは、以下を参照してください。

    • Aho AV. Algorithms for finding patterns in strings. In: van Leeuwen J. Handbook of Theoretical Computer Science, vol. A. New York: Elsevier; 1990. p. 255–300. 古典的な文字列照合アルゴリズムを概観しており、その一部はgrepで使われています。
    • Aho AV, Corasick MJ. Efficient string matching: an aid to bibliographic search. CACM. 1975;18(6):333–40. https://doi.org/10.1145/360825.360855. Aho–Corasick法を紹介しています。
    • Boyer RS, Moore JS. A fast string searching algorithm. CACM. 1977;20(10):762–72. https://doi.org/10.1145/359842.359859. Boyer–Moore法を紹介しています。
    • Faro S, Lecroq T. The exact online string matching problem: a review of the most recent results. ACM Comput Surv. 2013;45(2):13. https://doi.org/10.1145/2431211.2431212. 将来、grepの性能改善に役立つ可能性がある文字列照合アルゴリズムを概観しています。
    • Hakak SI, Kamsin A, Shivakumara P, Gilkar GA, Khan WZ, Imran M. Exact string matching algorithms: survey issues, and future research directions. IEEE Access. 2019;7:69614–37. https://doi.org/10.1109/ACCESS.2019.2914071. Faro & Lecroqより新しい概説で、性能よりも分類に重点を置いています。
    • Hume A, Sunday D. Fast string search. Software Pract Exper. 1991;21(11):1221–48. https://doi.org/10.1002/spe.4380211105. 現在では古くなったものの優れた概説であり、grepの初期開発に役立ちました。