18

検索している用語が固定値である文字列に対して単純な包含または置換操作を実行する必要があるたびに、サンプル入力を取得してプロファイリングを実行すると、コンパイルされた正規表現を使用すると、 Stringクラスの同等のメソッドを使用するよりもほぼ*常に高速です。

さまざまな方法を比較してみました（hs検索する「干し草の山」、検索ndlする「針」repl、置換値です。regex常にオプションを使用して作成されRegexOptions.Compiledます）：

  • hs.Replace( ndl, repl )vsregex.Replace( hs, repl )
  • hs.Contains( ndl )vsregex.IsMatch( hs )

2つのテクニックのどちらが速いか（1、2、3、および他の多くのテクニック）に焦点を当てたかなりの数の議論を見つけましたが、それらの議論は常に以下に焦点を当てているようです：

  1. 単純な操作には文字列バージョンを使用し、複雑な操作には正規表現を使用します（これは、生のパフォーマンスの観点からは、必ずしも良い考えではないようです）。
  2. テストを実行して2つを比較します（同等のテストの場合、正規表現バージョンの方が常にパフォーマンスが優れているようです）。

これがどのように当てはまるのかわかりません。正規表現エンジンは、同等の文字列バージョンよりも速く、サブ文字列の一致について2つの文字列をどのように比較しますか？これは、非常に小さいまたは非常に大きい検索スペース、小さいまたは大きい検索用語、または検索用語が検索スペースの早い段階または遅い段階にあるかどうかに当てはまるようです。

では、なぜ正規表現が高速なのですか？

*実際、文字列バージョンがコンパイルされた正規表現よりも高速であることを示すことができた唯一のケースは、空の文字列を検索する場合です。それ以外の場合、単一文字列から非常に長い文字列まで、同等の文字列メソッドよりもコンパイルされた正規表現によって高速に処理されます。

更新：コンパイル時に検索語がわかっている場合を調べていることを明確にする句を追加しました。動的または1回限りの操作の場合、正規表現をコンパイルするオーバーヘッドは、文字列メソッドを優先して結果を歪める傾向があります。

4

3 に答える 3

14

これがどのように当てはまるのかわかりません。正規表現エンジンは、同等の文字列バージョンよりも速く、サブ文字列の一致について2つの文字列をどのように比較しますか？

私は2つの理由を考えることができます：

  1. 正規表現は、ボイヤームーア文字（O（M / N））のようなスマートアルゴリズムを使用していますが、単純な文字列操作では、針を干し草の山の各位置（O（N * M））と単純に比較します。
  2. 彼らは実際には同じことをしていません。たとえば、一方はカルチャ不変のマッチングを実行し、もう一方はカルチャ依存のマッチングを実行する場合があります。これにより、パフォーマンスが異なる場合があります。
于 2012-09-14T17:06:03.833 に答える
6

基本クラスライブラリチームが書いたように：

[RegexOptions.Compiledの場合]では、最初にオペコードに解析する作業を行います。次に、Reflection.Emitを使用して、これらのオペコードを実際のILに変換するための作業も行います。ご想像のとおり、このモードでは、起動時間が長くなり、実行時間が短縮されます。実際には、コンパイルには起動に1桁ほど時間がかかりますが、実行時のパフォーマンスは30％向上します。

しかし、あなたは1つの重要なことを見逃しています：パターンは固定されています。これが常に当てはまるとは限らないことに注意してください。実行時に変更することはできません。パフォーマンスが30％以上向上すると、柔軟性が低下する場合があります。

于 2012-09-14T17:06:04.083 に答える
1

私自身の経験から、単純な文字列操作で正規表現ソリューションとカスタムパーサーのベンチマークを行った場合、正規表現ソリューションは少し遅くなります。それは彼らがしばしばバックトラックに苦しんでいるからです。

しかし、好奇心から、私はあなたの言うことが最も単純な例で本当に真実であるかどうかを確認するために少しテストを書きました。

これが私のテストです...

    private static Regex RegexSearch = new Regex("Audi A4", RegexOptions.Compiled);

    static void Main(string[] args)
    {            
        // warm up the JIT compiler
        FoundWithRegexIsMatch();
        FoundWithStringContains();
        FoundWithStringIndexOf();
        // done warming up

        int iterations = 100;
        var sw = new Stopwatch();

        sw.Restart();
        for (int i = 0; i < iterations; i++)
        {
            FoundWithRegexIsMatch();
        }
        sw.Stop();
        Console.WriteLine("Regex.IsMatch: " + sw.ElapsedMilliseconds + " ms");


        sw.Restart();
        for (int i = 0; i < iterations; i++)
        {
            FoundWithStringIndexOf();
        }
        sw.Stop();
        Console.WriteLine("String.IndexOf: " + sw.ElapsedMilliseconds + " ms");


        sw.Restart();
        for (int i = 0; i < iterations; i++)
        {
            FoundWithStringContains();
        }
        sw.Stop();
        Console.WriteLine("String.Contains: " + sw.ElapsedMilliseconds + " ms");
    }

    private static bool FoundWithStringContains()
    {
        return Resource2.csv.Contains("Audi A4");
    }

    private static bool FoundWithStringIndexOf()
    {
        return Resource2.csv.IndexOf("Audi A4") >= 0;
    }

    private static bool FoundWithRegexIsMatch()
    {
        return RegexSearch.IsMatch(Resource2.csv);
    }

持っているCSVファイル（約1.2 MB）に対してテストしています。そしてここに結果があります：

  • Regex.IsMatch：172ミリ秒
  • String.IndexOf：172ミリ秒
  • String.Contains：185ミリ秒

確かにあなたは正しいです。正規表現で特別なことを何もしていない場合、正規表現はString.Contains操作よりも少し高速です。ただし、 String.Containsにはわずかなオーバーヘッドがあり、呼び出しString.IndexOfはより高速で、実際Regex.IsMatchにはミリ秒 の時間に一致することがわかりました。

これらの同じタイミングは疑わしいです。コンパイル中に、これが実際に正規表現エンジンを通過する必要がないと判断されたのではないかと思います（上記で使用したパターンには正規表現固有の命令がないため）。Regex.IsMatch代わりに、kernel32.dllからFindNLSStringを呼び出すのと同じように簡略化することができますIndexOf。それは単なる推測です。

于 2012-09-14T20:10:45.567 に答える