概要
Golangで正規表現を扱うことになったので、ググったところgolangのサジェストワードに「遅い」というワードが出てきた。
なので、調査してみた。
Golangの正規表現
実装
上記のサイトはGolangで正規表現を扱うときに使われるregexpパッケージの公式ドキュメント。
ドキュメントによる処理速度に関する記述では
The regexp implementation provided by this package is guaranteed to run in time linear in the size of the input. (This is a property not guaranteed by most open source implementations of regular expressions.)
と書かれており、ざっくり日本語訳すると
「Golangの正規表現の実装は入力サイズに対して線形時間で処理されることが保証されている」
と書かれている。
さらに、ドキュメントには
The syntax of the regular expressions accepted is the same general syntax used by Perl, Python, and other languages. More precisely, it is the syntax accepted by RE2 and described at https://golang.org/s/re2syntax, except for \C.
と書かれており、GolangのregexpはRE2で実装されていることが分かる。
RE2
上記サイトはGoogleが提供しているRE2のオープンソース。
こちらによると、RE2の処理速度は入力文字に対して、線形時間で処理されることが保証されていることが書かれている。
つまり、GolangのregexpパッケージはRE2を元に実装されているので、入力文字数に対して線形時間で処理されるということらしい。
より詳しい話
上記のサイトはGolangの生みの親の一人であるRuss Coxによる正規表現の実装について書かれている。
サイトではイントロダクションでPerl 5.8.7とThompson NFAアルゴリズム（RE2で採用されているアルゴリズム）の処理速度の比較から始まっていた。
ざっくりとまとめると
Perlの正規表現の入力文字と処理速度の関係は指数関数のグラフになるが 、Thompson NFAは線形関数のグラフになる。
入力文字が29単語にマッチする正規表現を書いたときの処理時間はPerl 5.8.7は60秒かかるが、Thompson NFAは20秒ぐらいで済む。
