RE2を試してみた。 - 初学者の箸置

Google Code Searchで使われている正規表現ライブラリRE2が公開された。
http://code.google.com/p/re2/
PCRE系のバックトラック式（指数的時間、どこまでも伸びるスタック）に変わるものとして、Ken Thompsonのopen source grepで使われている fast DFA方式（多項式時間、固定スタック）で実装されているらしい。ちょと試してみようかと。

まずはPCREの速度測定

http://swtch.com/~rsc/regexp/regexp1.html
とのことで、試してみる。
PCREで(a?)^n(a)nをつくって実験。

#include <iostream>
#include <string>
#include <sys/time.h>

#include <pcrecpp.h>

long long gettime()
{
    struct timeval tv;
    ::gettimeofday(&tv, NULL) ;
    return tv.tv_sec * 1000000 + tv.tv_usec;
}

using namespace std;

main()
{
    long long t;
    for (int n = 1; n< 29; n++) {
        string s(n, 'a');
        string pat;

        for (int i = 0; i< n; i++) pat += string("a?");
        pat += s;

        pcrecpp::RE re(pat);

        t = gettime();

        if (!re.FullMatch(s)) { cerr << "something wrong!!" << endl; break;}

        cout << gettime() - t<< endl;;

    }
}

環境はちと古いんだけど Intel(R) Pentium(R) 4 CPU 2.40GHz　(cache 512 KB)。
じっこ。結果はus。

quartz% ./pcre
27
4
3
4
35
10
18
35
75
144
297
586
1222
2461
5053
9926
20053
41364
82266
166144
340380
692633
something wrong!!

なんと！ 23程度で死んだ。スタックオーバーフローだろうか？

真打 RE2では？

#include <iostream>
#include <string>
#include <sys/time.h>

#include <re2/re2.h>

using namespace std;

long long gettime()
{
        struct timeval tv;
        ::gettimeofday(&tv, NULL) ;
        return tv.tv_sec * 1000000 + tv.tv_usec;
}

main()
{
        long long t;
        for (int n = 1; n< 29; n++) {
                string s(n, 'a');
                string pat;

                for (int i = 0; i< n; i++) pat += string("a?");
                pat += s;

                t = gettime();
                if (!RE2::FullMatch(s, pat)) { cerr << "something wrong!!" << endl; break;}

                cout << gettime() - t<< endl;
        }
}

ほとんどいっしょ。ダサい。どうせならクラスで括り出せばよかった。まあいいや。

おお、スゴイ。確かに線形時間。しかしどちらもa?a のときがかなり遅い。最初のセットアップ、というかキャッシュの問題かな。というわけで、双方以下のようなダミー読みを入れてみた結果一発目も早くなった。

    if (!RE2::FullMatch("b", "b?b")) { cerr << "something wrong!!" << endl; exit(1);}

グラフ化してみる

PCRE

増えてくるとすごい遅い。本当にこの程度の正規表現でアウトとは・・・

RE2

確かに速い。CodeSearchでは速さが生命線だと思うので流石、としか言いようが無い。しかし、他のパターンでも試してみるべき。弱点を探してみようかなとか思う。

ちなみに、12くらいまでの結果をクローズアップして両者を比較すると

のようになっていて 8backtrack程度の「比較的」常識レベルの正規表現であればPCREの方が有利だったりする。

結論

RE2はええ