淨簡單的regex二次複雜

，而建設一個簡單的正則表達式我發現它有一個很奇怪性能特性，而輸入尺寸增大。淨簡單的regex二次複雜

這裏是有類似行爲的另一非常基本的正則表達式：

a+b

我用一個簡單的基準異形它：

Regex regex = new Regex("a+b", RegexOptions.Compiled); 

const int maxInputSize = 100; 
const int n = 1000; 

string input = ""; 
Stopwatch stopwatch = new Stopwatch(); 
for (int inputSize = 1; inputSize <= maxInputSize; ++inputSize) 
{ 
    input += 'a'; 

    stopwatch.Restart(); 
    for (int i = 0; i < n; ++i) 
    { 
     regex.Match(input); 
    } 
    stopwatch.Stop(); 

    Console.WriteLine(stopwatch.Elapsed.Ticks); 
}

它運行在字符串正則表達式「一」，「aa」，「aaa」，...以及測量每個字符串長度進行n次匹配所用的時間。

我知道了回溯問題（例如，如果正則表達式是像(a+a+)+b），但在這種情況下，即使考慮回溯我期望的線性複雜。

舉個例子，如果我們想匹配n次「A」這裏是工作流程我天真預期：

take first 'a' 
take second 'a' 
... 
take last 'a' 
ooops nothing more to take => backtracking 
release one 'a' and try to match 'b', nothing => backtracking 
... 
release second 'a' and retry to match 'b', nothing => backtracking 
release first 'a' 
ooops we're back at the beginning => no match

所以應該執行類似2N操作。

（本文檔似乎證實了這種複雜性應該是線性的：http://msdn.microsoft.com/en-us/library/dsy130b4.aspx）

而是我觀察二次複雜：

enter image description here

所以我的問題是：

1）是我對線性複雜度的期望不合理？
2）如果是，我錯過了什麼正則表達式匹配？
3）如果不是，我的基準是否有缺陷？爲什麼？ 4）如果我的預期和基準是正確的，那麼問題可能是什麼？

先感謝您的任何輸入。

來源

2013-10-06 Pragmateek

您可能希望提高樣品大小發生定時是在幾秒鐘內，而不是100的蜱爲您的時間提供可能不如正如你所期待的那樣。 –

@DarrenKopp：良好的話，但在這種情況下，樣本量與實驗一致：它需要毫秒的十分之一，甚至有更大的樣本量，我得到了相同的行爲。謝謝。 – Pragmateek

Regex.Match函數搜索子字符串匹配：引擎嘗試匹配從字符串的任何索引處開始的表達式，並給出O（n2）算法。您可以通過固定的正則表達式的字符串的開頭可能實現性能的線性：

Regex regex = new Regex("^a+b$", RegexOptions.Compiled);

來源

2013-10-06 00:47:13 Joni

當然> _ <！有了這個我有一個線性的複雜性，它是顯而易見的，爲什麼我的的複雜性是二次：在字符串滑動窗口是缺失的維度。感謝你及時的答覆。 :) – Pragmateek

淨簡單的regex二次複雜

回答

相關問題