最近あんまりパフォーマンス的によくない正規表現を見かけたので、いくつかのパターンについて正規表現をいろんな言語で試してみて実行時間を測ってみた(ついでに最悪計算量についてゆるふわに考えてみた)
実際には正規表現エンジンの実装(NFAやDFAとか？)やバージョン、オプション(？)によると思いますしなんとなくの傾向という感じです
やること
以下の正規表現についてパターンマッチされる対象の文字列の長さ\(L\)が増えたときに、1回マッチするか調べる時間がどれぐらい伸びるかを調べます
.*aa.*ba.*b.*ca(a|aa)*b
計測方法
以下の言語についてIdeoneで実行してみて実際に測ってみた時間を載せます(括弧内はIdeoneに書かれていたバージョン)
- Ruby (ruby-2.1)
- Python (python 2.7.10)
- PHP (php 5.6.4)
- Java (sun-jdk-8u51)
- Go (1.4.2)
それぞれの言語についてIdeoneのコードを貼っておきます
あまり詳しくないのでより効率的な書き方があったらコメントいただけるとうれしいです
Ideoneの実行時間を測っているだけなので、文字列の生成時間なども含まれてます
以下のようなコードを使いました
Ruby
p ('z'*1000000000).match(/.*a/)
Python
import re re.search(r'.*a', 'a' * 1000000000)
PHP
<?php echo preg_match('/.*a/', str_repeat('z', 1000000000));
Java
import java.util.regex.Matcher; import java.util.regex.Pattern; class Main { public static void main (String[] args) throws java.lang.Exception { Pattern p = Pattern.compile(".*a"); Matcher m = p.matcher(new String(new char[10000000]).replace("\0", "z")); m.find(); } }
Go
package main import "regexp" import "strings" func main() { regexp.MustCompile(`.*a`).MatchString(strings.Repeat("z", 100000000)) }
結果
最初はグラフにしようと思ったのですが、かかる時間が違いすぎて一つのグラフに書くのが無理だったので言語別にそれぞれの時間を書いておきます
.*a
正規表現がマッチしない場合全部の位置を始まりとして.*を試して最後まで行ってaが見つかるまで1文字ずつバックトラックして確認するので最悪計算量は\(O(L^2)\)ぐらい
- 探される対象の文字列:
'z'の繰り返し
Ruby: .*a
文字列の長さを2倍にしたら実行時間も2倍に伸びているので\(O(L)\)っぽい
明らかにマッチしない時はなんらかの高速化が動いているのかな？
| 文字数 | 実行時間(秒) |
| 500,000,000 | 3.78 |
| 1,000,000,000 | 7.57 |
a.*b
今度こそ\(O(L^2)\)になるのを期待
- 探される対象の文字列:
'a'の繰り返し
a.*b.*c
バックトラックが2重に起こるので\(O(L^3)\)になることが予想される
- 探される対象の文字列:
'a'の繰り返し + 'b'の繰り返し
a(a|aa)*b
同じ文字がaとaaの2つの状態になりうるので最悪計算量は指数的に増えていくはず
- 探される対象の文字列:
'a'の繰り返し
ちなみに以下の記事では(¥w|_){1,64}という部分を含む正規表現で処理に長時間かかった話が書かれています(\wには_が含まれる)
遅いッ！遅すぎるッ！Java の正規表現のお話。 - Cybozu Inside Out | サイボウズエンジニアのブログ
同様に(.*)*aのようなくりかえしのくりかえしを含むような正規表現の場合は明らかにひどいことになります
まとめ
- (雑に考えると)正規表現に含まれる、末尾以外の繰り返し(
*や+)の数だけ最悪計算量の次数が増える(バックトラックのせい) - \(O(L^2)\)の正規表現でも数万文字ぐらいで、秒単位で時間がかかるようになる
- 同一の文字列を含む論理和のくりかえしや、同じ文字のくりかえしのくりかえしは指数的に最悪計算量が増えていって、数十文字で正規表現の計算ができなくなる
- 正規表現エンジンごとになんらかの高速化(？)が入っていて遅くなりそうなパターンでも遅くならないことがある
- Goの正規表現はひどいパターンの時でも入力に対して線形な時間で終わることが保証されているらしい
The regexp implementation provided by this package is guaranteed to run in time linear in the size of the input.
https://golang.org/pkg/regexp/
参考(というか正規表現のパフォーマンスとかについての記事ではてなブックマークしてたのを羅列しただけ)
正規表現を使ったDoS – ReDoS | yohgaki's blog
ReDoSの回避 | yohgaki's blog
