最近あんまりパフォーマンス的によくない正規表現を見かけたので、いくつかのパターンについて正規表現をいろんな言語で試してみて実行時間を測ってみた(ついでに最悪計算量についてゆるふわに考えてみた)
実際には正規表現エンジンの実装(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)\)ぐらい
Ruby: .*a
文字列の長さを2倍にしたら実行時間も2倍に伸びているので\(O(L)\)っぽい
明らかにマッチしない時はなんらかの高速化が動いているのかな？
| 文字数 |
実行時間(秒) |
| 500,000,000 |
3.78 |
| 1,000,000,000 |
7.57 |
Python: .*a
文字列の長さを2倍にしたら実行時間は4倍に伸びているので\(O(L^2)\)
PHP: .*a
文字列の長さを2倍にしたら実行時間も2倍に伸びているので\(O(L)\)
| 文字数 |
実行時間(秒) |
| 500,000,000 |
1.40 |
| 1,000,000,000 |
2.79 |
ちなみにPHPでは正規表現がa*bの時には'a'の繰り返しとマッチさせると\(O(L^2)\)になりました
Java: .*a
文字列の長さを2倍にしたら実行時間は4倍に伸びているので\(O(L^2)\)
Go: .*a
\(O(L)\)
| 文字数 |
実行時間(秒) |
| 500,000,000 |
4.34 |
| 100,000,000 |
8.7 |
a.*b
今度こそ\(O(L^2)\)になるのを期待
Ruby: a.*b
文字列の長さを2倍にしたら実行時間も4倍に伸びているので\(O(L^2)\)
Python: a.*b
文字列の長さを2倍にしたら実行時間は4倍に伸びているので\(O(L^2)\)
PHP: a.*b
文字列の長さを2倍にしたら実行時間も4倍に伸びているので\(O(L^2)\)
Java: a.*b
文字列の長さを2倍にしたら実行時間は4倍に伸びているので\(O(L^2)\)
Go: a.*b
Goだけは\(O(L)\)でした
| 文字数 |
実行時間(秒) |
| 10,000,000 |
1.15 |
| 20,000,000 |
2.29 |
a.*b.*c
バックトラックが2重に起こるので\(O(L^3)\)になることが予想される
- 探される対象の文字列:
'a'の繰り返し + 'b'の繰り返し
Ruby: a.*b.*c
文字列の長さを2倍にしたら実行時間も8倍に伸びているので\(O(L^3)\)
Python: a.*b.*c
文字列の長さを2倍にしたら実行時間は8倍に伸びているので\(O(L^3)\)
PHP: a.*b.*c
何故か\(O(L^3)\)どころではないペースで増加しているようにみえる。なんでだろ？
Java: a.*b.*c
文字列の長さを2倍にしたら実行時間は8倍に伸びているので\(O(L^3)\)
Go: a.*b.*c
文字列の長さを2倍にしたら実行時間は2倍に伸びているので\(O(L)\)っぽい。速い！？
| 文字数 |
実行時間(秒) |
| 10,000,000 |
2.96 |
| 20,000,000 |
5.89 |
Ruby: a(a|aa)*b
数文字変わっただけで実行時間が数倍になる
Python: a(a|aa)*b
数文字変わっただけで実行時間がすごい勢いで増えている
PHP: a(a|aa)*b
このパターンではPHPの正規表現エンジンを倒すことができなかった(？)
| 文字数 |
実行時間(秒) |
| 1,000,000,000 |
0.44 |
Go: a(a|aa)*b
文字数を2倍にしたら実行時間も2倍ぐらいになっている
| 文字数 |
実行時間(秒) |
| 10,000,000 |
1.98 |
| 20,000,000 |
3.96 |
まとめ
- (雑に考えると)正規表現に含まれる、末尾以外の繰り返し(
*や+)の数だけ最悪計算量の次数が増える(バックトラックのせい)
- \(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/
