正規表現のパフォーマンス比較 : 繰り返し回数

About

正規表現を用いてある文字列が何回か繰り返し現れることを検出するにはいくつかの方法があります。基本的な2つは次の通りです。ここでは 0 の3回の繰り返しを検出するとします。

(000)
(0{3})

果たしてパフォーマンスに違いは出るのでしょうか。気になったので簡単に調べてみました。ここでの実験環境は次の通りです。言語、バージョン、実行機などの環境によって大きく差が出る可能性がある点に注意してください。特にここでの実験は簡単な正規表現で実験していますから、複雑化するときにはパフォーマンスに大きな差がみられるようになるかもしれません。

Windows8 64bit
Corei7 3.4GHz
C#(.Netframework 4.5)

実験と結果

結論から先に述べると、1 のパターンの方が早くなります。ただし今回実験したような環境下ではパフォーマンスに大きな差はないようです。テストコードは次の通りです。

class Program
{
    static string text
        = "000 test 00 test 000 test 0000 test 00000 test 0 test 00 test";
    static string regex1 = "000";
    static string regex2 = "0{3}";

    static void Main(string[] args)
    {
        MatchCollection matches;
        Stopwatch stopWatch = new Stopwatch();

        //[Pattern 1]
        stopWatch.Restart();
        for (int i = 0; i < 1000000; i++)
            matches = Regex.Matches(text, regex1);
        stopWatch.Stop();
        Console.WriteLine(stopWatch.Elapsed.Milliseconds);

        //[Pattern 2]
        stopWatch.Restart();
        for (int i = 0; i < 1000000; i++)
            matches = Regex.Matches(text, regex2);
        stopWatch.Stop();
        Console.WriteLine(stopWatch.Elapsed.Milliseconds);

        Console.ReadLine();
    }
}

30回以上繰り返し実行しましたが、どちらとも 240msec - 260msec の範囲に収まります。平均して 1 のパターンの方が 5msec - 8msec 程度早いのは間違いありませんが、極まれに 2 のパターンの方が早くなったり、同じ処理時間に収まることもありました。これらの原因はわかりません。

複雑なパターンを検証するときは更に差が出るかもしれませんが、繰り返し回数が決まったパターンを検出するときには、その回数の数だけ文字を羅列した方が良いのかもしれません。複雑化した場合にも十分に検証が必要でしょうが、1,000,000回の施行でこれだけの差しか出ませんでした。

コンパイル済みの正規表現

C#(.net) の正規表現にはコンパイル済みの正規表現というものがあります。詳細は割愛しますが、折角C#を使用しているので試してみました。処理時間は 170msec 前後になるので、コンパイルしないものと比較して 80msec 程度の大きく差となります。3 のパターンと 4 のパターンに関してはやはり大きな差は見られませんでした。むしろ処理時間は互いに前後することがあり、その差も 2msec 程度しか見られません。コンパイル済みの正規表現が利用できる環境下で繰り返し利用する正規表現は積極的にコンパイルした方がよさそうです。

class Program
{
    static string text
        = "000 test 00 test 000 test 0000 test 00000 test 0 test 00 test";
    static string regex1 = "000";
    static string regex2 = "0{3}";
    static Regex preCompliedRegex1 = new Regex(regex1);
    static Regex preCompliedRegex2 = new Regex(regex2);

    static void Main(string[] args)
    {
        MatchCollection matches;
        Stopwatch stopWatch = new Stopwatch();

        //[Pattern 1]
        stopWatch.Restart();
        for (int i = 0; i < 1000000; i++)
            matches = Regex.Matches(text, regex1);
        stopWatch.Stop();
        Console.WriteLine(stopWatch.Elapsed.Milliseconds);

        //[Pattern 2]
        stopWatch.Restart();
        for (int i = 0; i < 1000000; i++)
            matches = Regex.Matches(text, regex2);
        stopWatch.Stop();
        Console.WriteLine(stopWatch.Elapsed.Milliseconds);

        //[Pattern 3]
        stopWatch.Restart();
        for (int i = 0; i < 1000000; i++)
            preCompliedRegex1.Match(text);
        stopWatch.Stop();
        Console.WriteLine(stopWatch.Elapsed.Milliseconds);

        //[Pattern 4]
        stopWatch.Restart();
        for (int i = 0; i < 1000000; i++)
            preCompliedRegex2.Match(text);
        stopWatch.Stop();
        Console.WriteLine(stopWatch.Elapsed.Milliseconds); 

        Console.ReadLine();
    }
}

補足 : コンパイル済み正規表現が定義される言語・環境

次の言語ではコンパイル済みの正規表現が利用できるようです。

C#
Javascript
Python
Perl
PHP
Ruby