regex比較 - 初学者の箸置

通りすがりの方から「鬼車はー？」というリクエストをもらったので*1・・・全体書き直してフレームワークみたいにしてみた。
http://github.com/tkuro11/RegProf

_Profベースクラス

例のバックトラックパターンのみ（しかも1から28固定）というしょぼいプロファイルだけしかとらないんだけど、とりあえずクラスにくくりだしてみた。
_Profクラスをベースにして、これの仮想関数になっている RE()を各regexエンジン用に書き加えてサブクラス化する。その後、ベースクラスのインスタンスメソッド Prof()を呼び出すと自分の RE()を読んでその時間を返す、と言った感じの方式、例えば前回の RE2であれば、

#include <re2/re2.h>

#include "_Prof.h"

struct RE2Prof : public _Prof {
    bool RE(string& s, string& pat) {
        return RE2::FullMatch(s, pat);
    }
};

main()
{
    (new RE2Prof())->Prof();
}

のように書けるようにした。

oniguruma

onigurumaは rubyにも採用されている事で有名なC言語ベースのregexライブラリ。実はperlやjava, posix_*などruby以外にも幅広いタイプの正規表現も受け付けるため、一言にonigurumaとの比較、とは言えない。どの文法エンジンで？という条件つきになる。
色々試す為にコンストラクタに文法を指定するようにして、スクリプトでまわした。
実験してみるとPCREのように途中で死んだりしない。すばらしい（いや、、、その、、、）
結果をグラフにするとこんな感じ。

バックトラック系とDFA系に綺麗に分かれてるので、 ONIG_SYNTAX_RUBYと ONIG_SYNTAX_GREPを代表としておく。

boost::regex

おまけでboostも作ってみた。詳しくないのでどんなクラスの正規表現が扱えるのかよくわかってないんだけど、とりあえず非常に速い。

n	経過時間[us]
1	9
2	10
3	15
4	10
5	10
6	17
7	13
8	14
9	15
10	16
11	29
12	21
13	21
14	22
15	23
16	24
17	26
18	27
19	27
20	29
21	30
22	45
23	36
24	36
25	38
26	38
27	39
28	41

てな感じの速度。

で、対決

n	RE2	PCRE	ONIG_GREP	ONIG_RUBY	boost
1	5	27	3	5	9
2	10	28	4	9	10
3	6	31	4	9	16
4	8	33	4	13	11
5	10	37	9	11	12
6	15	41	4	13	18
7	23	46	4	17	15
8	40	55	6	27	16
9	79	56	10	33	17
10	147	61	6	53	18
11	299	69	9	89	31
12	599	85	6	160	21
13	1220	82	6	300	22
14	2508	89	7	576	23
15	5217	104	7	1124	24
16	10748	102	11	2213	26
17	16250	118	8	4401	27
18	29530	117	8	7843	27
19	61318	136	8	11630	29
20	124776	135	9	23358	30
21	256804	152	9	46802	31
22	520372	162	10	92712	46
23	NA	170	10	185618	37
24	NA	176	11	371303	37
25	NA	198	11	742349	39
26	NA	196	15	1482128	40
27	NA	223	12	2971400	41
28	NA	224	12	5922651	42

グラフにすると

こんな感じ。風雲急を告げる１０くらいまでの部分を拡大すると

こんな感じで、単純には小さなパターンではONIG_GREP = boost = PCRE = ONIG_RUBY >>> RE2で、パターンが大きくなってくると ONIG_GREP > boost >> RE2 >>>>> ONIG_RUBY >> PCRE(しかも失格)と言う感じなのかな。この実験のようなパターンでは、普通レベルのパターンならRE2はそんなに優位ではない、というのが本当のところのようだ。
しかしRE2は正規表現セットとして PCREとほぼ同じセットを扱えるので、そう単純には比較できない。boost::regexとかがどういうセットか良く知らないので、もう少し勉強してみよう、という感じ。まだまだ未熟な僕でした・・・

結論

サービスアタック（最悪時）とか考えないならonigurumaで良いよ！！（マテ

*1:遅くなりましてすみません

n	経過時間[us]
1	9
2	10
3	15
4	10
5	10
6	17
7	13
8	14
9	15
10	16
11	29
12	21
13	21
14	22
15	23
16	24
17	26
18	27
19	27
20	29
21	30
22	45
23	36
24	36
25	38
26	38
27	39
28	41

n	経過時間[us]
1	9
2	10
3	15
4	10
5	10
6	17
7	13
8	14
9	15
10	16
11	29
12	21
13	21
14	22
15	23
16	24
17	26
18	27
19	27
20	29
21	30
22	45
23	36
24	36
25	38
26	38
27	39
28	41

n	経過時間[us]
1	9
2	10
3	15
4	10
5	10
6	17
7	13
8	14
9	15
10	16
11	29
12	21
13	21
14	22
15	23
16	24
17	26
18	27
19	27
20	29
21	30
22	45
23	36
24	36
25	38
26	38
27	39
28	41