. NET 간단한 정규식 2 차 복잡도

Question

정규식을 작성하는 동안 입력 크기가 증가하는 동안 상당히 성능 인이라는 프로파일을 발견했습니다.

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); 
} 

그것은 문자열에 정규식을 실행 "A"여기

비슷한 동작을 가진 다른 정말 기본 정규식 , "aa", "aaa"... 문자열의 각 길이가 일치하는 데 걸린 시간을 측정합니다.

나는 (정규식 (a+a+)+b 같은했다 예를 들어, 경우) 되돌아 문제를 인식 합니다만,이 경우에도 나는 선형 복잡성 예상 되돌아 고려.

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 작업 같은 것을 실행한다 : 예를 들어

우리가 N 시간을 일치시킬 경우 '는이'여기 내가 순진 예상되는 흐름이다.

는 (이 문서는 선형해야하는 복잡성을 확인하는 것 : http://msdn.microsoft.com/en-us/library/dsy130b4.aspx)

을하지만 그 대신 나는 차 복잡성 관찰 :

그래서 제 질문은 다음과 같습니다

을
• 1) 선형 복잡성에 대한 내 기대가 부당했습니다. ?
• 2) 그렇다면 정규식 일치에 대해 무엇을 놓치고 있습니까?
• 3) 아니오라면 내 벤치 마크에 결함이 있습니까? 왜?
• 4) 내 기대치와 벤치 마크가 맞으면 무엇이 문제가 될 수 있습니까?

미리 알려 주시기 바랍니다.

Answer 1

Regex.Match 함수는 부분 문자열 일치를 찾습니다. 엔진은 문자열의 임의 색인에서 시작하는 표현식과 일치하도록 시도하여 O (n²) 알고리즘을 제공합니다. 당신은 아마 문자열의 시작에 정규식을 고정하여 선형 성능을 달성 할 수

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