読者です 読者をやめる 読者になる 読者になる

唯物是真 @Scaled_Wurm

プログラミング(主にPython2.7)とか機械学習とか

正規表現がどれぐらい遅くなるか(計算量?)を調べてみた

最近あんまりパフォーマンス的によくない正規表現を見かけたので、いくつかのパターンについて正規表現をいろんな言語で試してみて実行時間を測ってみた(ついでに最悪計算量についてゆるふわに考えてみた)
実際には正規表現エンジンの実装(NFAやDFAとか?)やバージョン、オプション(?)によると思いますしなんとなくの傾向という感じです

やること

以下の正規表現についてパターンマッチされる対象の文字列の長さ\(L\)が増えたときに、1回マッチするか調べる時間がどれぐらい伸びるかを調べます

  • .*a
  • a.*b
  • a.*b.*c
  • a(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
Python: .*a

文字列の長さを2倍にしたら実行時間は4倍に伸びているので\(O(L^2)\)

文字数 実行時間(秒)
50,000 1.49
100,000 5.95
PHP: .*a

文字列の長さを2倍にしたら実行時間も2倍に伸びているので\(O(L)\)

文字数 実行時間(秒)
500,000,000 1.40
1,000,000,000 2.79

ちなみにPHPでは正規表現がa*bの時には'a'の繰り返しとマッチさせると\(O(L^2)\)になりました

文字数 実行時間(秒)
100,000 2.24
200,000 8.93
Java: .*a

文字列の長さを2倍にしたら実行時間は4倍に伸びているので\(O(L^2)\)

文字数 実行時間(秒)
10,000 1.19
20,000 4.6
Go: .*a

\(O(L)\)

文字数 実行時間(秒)
500,000,000 4.34
100,000,000 8.7

a.*b

今度こそ\(O(L^2)\)になるのを期待

  • 探される対象の文字列: 'a'の繰り返し

Ruby: a.*b

文字列の長さを2倍にしたら実行時間も4倍に伸びているので\(O(L^2)\)

文字数 実行時間(秒)
10,000 0.61
20,000 2.4
Python: a.*b

文字列の長さを2倍にしたら実行時間は4倍に伸びているので\(O(L^2)\)

文字数 実行時間(秒)
50,000 1.49
100,000 5.95
PHP: a.*b

文字列の長さを2倍にしたら実行時間も4倍に伸びているので\(O(L^2)\)

文字数 実行時間(秒)
10,000 0.58
20,000 2.34
Java: a.*b

文字列の長さを2倍にしたら実行時間は4倍に伸びているので\(O(L^2)\)

文字数 実行時間(秒)
10,000 1.19
20,000 4.57
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)\)

文字数 実行時間(秒)
1,000 0.77
2,000 5.98
Python: a.*b.*c

文字列の長さを2倍にしたら実行時間は8倍に伸びているので\(O(L^3)\)

文字数 実行時間(秒)
2,000 0.63
4,000 4.91
PHP: a.*b.*c

何故か\(O(L^3)\)どころではないペースで増加しているようにみえる。なんでだろ?

文字数 実行時間(秒)
1,200 0.44
2,400 10.12
Java: a.*b.*c

文字列の長さを2倍にしたら実行時間は8倍に伸びているので\(O(L^3)\)

文字数 実行時間(秒)
1,000 1.51
2,000 11.41
Go: a.*b.*c

文字列の長さを2倍にしたら実行時間は2倍に伸びているので\(O(L)\)っぽい。速い!?

文字数 実行時間(秒)
10,000,000 2.96
20,000,000 5.89

a(a|aa)*b

同じ文字がaaaの2つの状態になりうるので最悪計算量は指数的に増えていくはず

  • 探される対象の文字列: 'a'の繰り返し

ちなみに以下の記事では(¥w|_){1,64}という部分を含む正規表現で処理に長時間かかった話が書かれています(\wには_が含まれる)
遅いッ!遅すぎるッ!Java の正規表現のお話。 - Cybozu Inside Out | サイボウズエンジニアのブログ

同様に(.*)*aのようなくりかえしのくりかえしを含むような正規表現の場合は明らかにひどいことになります

Ruby: a(a|aa)*b

数文字変わっただけで実行時間が数倍になる

文字数 実行時間(秒)
34 1.1
37 4.59
Python: a(a|aa)*b

数文字変わっただけで実行時間がすごい勢いで増えている

文字数 実行時間(秒)
23 1.38
26 11.15
PHP: a(a|aa)*b

このパターンではPHPの正規表現エンジンを倒すことができなかった(?)

文字数 実行時間(秒)
1,000,000,000 0.44
Java: a(a|aa)*b

指数的に増えてる

文字数 実行時間(秒)
34 1.66
37 6.8
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/

参考(というか正規表現のパフォーマンスとかについての記事ではてなブックマークしてたのを羅列しただけ)

blog.cybozu.io
developers.eure.jp
blog.shin1x1.com
postd.cc
postd.cc
d.hatena.ne.jp
正規表現を使ったDoS – ReDoS | yohgaki's blog
ReDoSの回避 | yohgaki's blog

-->