18

每次我必须对字符串进行简单的包含或替换操作时，我正在搜索的术语是一个固定值，我发现如果我获取样本输入并对其进行一些分析，使用编译的正则表达式是几乎* 总是比使用 String 类中的等效方法快。

我试过比较各种方法（hs是要搜索的“干草堆”，ndl是要搜索的“针”，repl是替换值。regex总是使用RegexOptions.Compiled选项创建）：

  • hs.Replace( ndl, repl )对比regex.Replace( hs, repl )
  • hs.Contains( ndl )对比regex.IsMatch( hs )

我发现很多讨论都集中在这两种技术中哪一种更快（1、2、3和其他许多技术），但这些讨论似乎总是集中在：

  1. 对简单操作使用字符串版本，对复杂操作使用正则表达式（从原始性能的角度来看，这甚至不一定是一个好主意），或者
  2. 运行测试并比较两者（对于等效测试，正则表达式版本似乎总是表现更好）。

我不明白这怎么可能是这种情况：正则表达式引擎如何比等效字符串版本更快地比较任何两个字符串的子字符串匹配？这似乎适用于非常小或非常大的搜索空间，或小或大的搜索词，或者搜索词是否出现在搜索空间的早期或晚期。

那么，为什么正则表达式更快呢？

* 事实上，我设法证明字符串版本比编译的正则表达式更快的唯一情况是在搜索空字符串时！任何其他情况，从单个字符串到非常长的字符串，编译的正则表达式比等效的字符串方法处理得更快。

更新：添加了一个子句来阐明我正在查看在编译时已知搜索词的情况。对于动态或一次性操作，编译正则表达式的开销往往会使结果偏向于字符串方法。

4

3 回答 3

14

我不明白这怎么可能是这种情况：正则表达式引擎如何比等效字符串版本更快地比较任何两个字符串的子字符串匹配？

我可以想到两个原因：

  1. 正则表达式使用一些智能算法，如Boyer Moore (O(M/N))，而简单的字符串操作只是将针与大海捞针中的每个位置进行比较 (O(N*M))。
  2. 他们并没有真正做同样的事情。例如，一个可能进行文化不变匹配，而另一个进行文化相关匹配，这可能会产生性能差异。
于 2012-09-14T17:06:03.833 回答
6

正如基类库团队所写：

在 [RegexOptions.Compiled 的情况下]，我们首先进行解析为操作码的工作。然后我们还做更多的工作来使用 Reflection.Emit 将这些操作码转换为实际的 IL。可以想象，这种模式以增加的启动时间换取更快的运行时间：实际上，编译需要大约一个数量级的时间才能启动，但运行时性能提高了 30%。

但是，您忽略了一件重要的事情：Pattern is fixed。请注意，情况并非总是如此。您无法在运行时更改它！在某些情况下，灵活性会下降超过 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);
    }

我正在针对我拥有的大约 1.2 MB 的 CSV 文件进行测试。结果如下：

  • 正则表达式.IsMatch：172 毫秒
  • String.IndexOf：172 毫秒
  • 字符串。包含：185 毫秒

确实你是对的。当你没有在正则表达式中做任何花哨的事情时，正则表达式比String.Contains操作快一点。但是，我发现String.Contains 中存在一点点开销，并且调用String.IndexOf速度更快，并且实际上匹配Regex.IsMatch到毫秒的时间。

这些相同的时间是可疑的。我想知道在编译过程中是否确定这实际上不需要通过正则表达式引擎（因为我上面使用的模式中没有特定于正则表达式的指令）。相反，它可以被简化，以便Regex.IsMatch从 kernel32.dll 对 FindNLSString 进行相同的调用IndexOf。这只是一个猜测。

于 2012-09-14T20:10:45.567 回答