Slow Regex performance

Question

Код ниже содержит регулярное выражение, предназначенное для извлечения строкового литерала C#, но производительность соответствия регулярных выражений для строк ввода более чем нескольких символов является горькой.

class Program 
{ 
    private static void StringMatch(string s) 
    { 
     // regex: quote, zero-or-more-(zero-or-more-non-backslash-quote, optional-backslash-anychar), quote 
     Match m = Regex.Match(s, "\"(([^\\\\\"]*)(\\\\.)?)*\""); 
     if (m.Success) 
      Trace.WriteLine(m.Value); 
     else 
      Trace.WriteLine("no match"); 
    } 

    public static void Main() 
    { 
     // this first string is unterminated (so the match fails), but it returns instantly 
     StringMatch("\"OK"); 

     // this string is terminated (the match succeeds) 
     StringMatch("\"This is a longer terminated string - it matches and returns instantly\""); 

     // this string is unterminated (so the match will fail), but it never returns 
     StringMatch("\"This is another unterminated string and takes FOREVER to match"); 
    } 
} 

Я могу реорганизовать регулярное выражение в другой форме, но может кто-нибудь дать объяснение, почему производительность настолько плохо?

Answer 1

Вы работаете в catastrophic backtracking:

Давайте упростить регулярное выражение немного (без сбежавших кавычек и без второй необязательной группы, потому что, как и в своем комментарии, это не имеет значение для тестируемых строк):

"(([^\\"]*))*" 

([^\\"]*) соответствует любой строке, кроме кавычек или обратных косых черт. Этот снова заключен в необязательную группу, которая может повторяться сколько угодно раз.

Теперь для строки "ABC, движок регулярных выражений должен попробовать следующие перестановки:

• ", ABC
• ", ABC, <empty string>
• ", AB, C
• ", AB, C, <empty string>
• ", AB, <empty string>, C
• ", AB, <empty string>, C, <empty string>
• ", <empty string>, AB, C
• ", <empty string>, AB, C, <empty string>
• ", <empty string>, AB, <empty string>, C, <empty string>
• ", <empty string>, AB, <empty string>, C
• ", A, BC
• ", A, BC, <empty string>
• ", A, <empty string> , BC
• ", <empty string>, A, BC
• и т.д.
• ", A, B, C
• ", A, B, C, <empty string>
• ", A, B, <empty string>, C
• и т.д. и т.п.

каждый из которых затем терпит неудачу, потому что нет следования ng ".

Кроме того, вы проверяете только подстроки вместо того, чтобы заставить регулярное выражение соответствовать всей строке. И вы обычно хотите использовать дословные строки для регулярных выражений, чтобы сократить количество требуемых обратных косых черт. Как об этом:

foundMatch = Regex.IsMatch(subjectString, 
    @"\A  # Start of the string 
    ""  # Match a quote 
    (?:  # Either match... 
    \\.  # an escaped character 
    |  # or 
    [^\\""] # any character except backslash or quote 
    )*  # any number of times 
    ""  # Match a quote 
    \Z  # End of the string", 
    RegexOptions.IgnorePatternWhitespace); 

Answer 2

Попробуйте

Match m = Regex.Match(s, @"'.*?(?<=[^\\](\\\\)*)'".Replace("'", "\"")); 

Это будет "разумно" игнорировать даже количество \. Это потому, что " закрывает строку, \" не делает, \\" делает (потому что первый обратный слеш вторую), \\\" не ...

.*? ленивый квантор. Вы можете даже использовать стандартный квантор .*. Я скажу, что, возможно, вы должны привязать свое регулярное выражение к ^ и $.

Я использую заменить, потому что миновать двойные кавычки дал мне головные боли :-)

Я добавлю, что с 4k текстом оно мгновенно на моем компьютере, как в матче и не совпадают.

В качестве альтернативы:

Match m = Regex.Match(s, @"^'(?>([^'\\]|\\.)*)'$".Replace("'", "\"")); 

Объяснение:

(?>) disables backtracking 

^ begin of the string 

то есть попеременное конструкцию (0 или более раз, то *):

[^'\\] any non-quote and non backslash 

\\. or a backslash followed by another character (that is escaped) 

$ end of the string 

Это тоже является очень быстро, и читать его довольно легко.

Answer 3

EDIT

Здесь вы идете: "\"([^\\\\\"]|\\\\.)*\""

Чтобы объяснить, после того, как C# избежала строку, которую вы получите это регулярное выражение: "([^\\"]|\\.)*"

Значение:

"    #start with a quote 
(
    [^\\"]  #match a non backslash or quote 
    |   #or 
    \\.   #backslash something 
)     
*    #And repeat 
"    #end with a quote 

По не влагалищ ваш * вы не получаете expone nutial или бесконечный цикл, и он мгновенно возвращается для меня.

Answer 4

Я думаю, что @Tim Pietzcker дал лучшее объяснение о возврате назад.

С помощью различных тестов вокруг (мой собственный включен) это быстрые способы:

Метод 1, разворачивая

" [^"\\]* (?: \\. [^"\\]*)* " 

Метод 2, чередование

" (?: \\. | [^"\\]+)* " 

Метод 1, может опережать 2 по существенной марже.

Информация

Я думаю, что его очень трудно объяснить катастрофические откаты. Даже признание этого иногда трудно, если только оно не очень очевидно. Затем в критичных по времени приложениях иногда полезно делать некоторые тесты.

В этом вопросе цитирования я хотел бы добавить новые подходы к эталонному шаблону perl (5.10 engined), чтобы увидеть, как он это делает. Каждый двигатель немного отличается. Если вам все равно, вот образец.

Образцы регулярных выражений против времени с использованием сильно процитированной и экранированной строки
повторяется 100 000 раз каждый.

(?x-ism:" ((?: \\?.)*?) ")
код принял: 14.7031 стандартной даты секунд (14,58 USR + 0.00 SYS = 14.58 CPU)

(?x-ism:" (.*? (?<!\\) (?:\\{2})*) ")
код Принимал: 12.8435 стандартной даты секунд (12,75 USR + 0.00 SYS = 12,75 CPU)

(?x-ism:" ((?: [^\\"] | \\.)*) ")
код принял: 10.3123 (сек стандартной даты 10.27 USR + 0.00 SYS = 10,27 CPU)

(?x-ism: " ((?: [^"\\]+ | (?:\\.)+)*) ")
код принял: 8.39063 стандартной даты сек (8,39 USR + 0.00 SYS = 8.39 CPU)

(?x-ism: " ((?: [^"\\]+ | \\.)*) ")
код принял: 8.7498 стандартной даты сек (8,75 USR + 0.00 SYS = 8.75 CPU)

(?x-ism: " ((?: \\. | [^"\\]+)*) ")
код принял: 8.5623 секунд стандартной даты (8,44 + 0,00 USR SYS = 8.44 CPU)

(?x-ism: " ([^"\\]* (?: \\. [^"\\]*)*) ")
код принял: 7.79661 сек (стандартной даты 7.80 + 0.00 USR SYS = 7,80 ЦП)

(?x-ism: (?> " ((?: [^"\\] | \\.)* ")))
код взял: 10.5156 (сек стандартной даты 10.52 USR + 0.00 SYS = 10,52 CPU)

Answer 5

Вот что я хотел бы использовать:

"[^\n"\\]*(?:\\.[^\n"\\]*)*" 

@sln правильно о unrolled- петлевый подход является самым быстрым, но я бы уточнил его немного больше, исключив переводы строк, которые недопустимы в старомодных строковых литералах.Часть \\. в порядке, но [^"\\] необходимо изменить на [^\n"\\]. Кроме того, если мы говорим о извлечении строковых литералов, мы не можем привязывать регулярное выражение с \A и \Z.

Я использовал RegexBuddy для сравнения производительности вашего регулярного выражения, регулярного выражения Тима без якорей, и этого. Я поместил курсор перед открывающей цитатой в каждом из ваших строк образца и используется «Debug Here», и эти результаты:

original regex  : "(([^\\"\n]*)(\\.)?)*" 

"OK     : failed in 101 steps 

"This is a longer... : matched in 12 steps 

"This is another... : gave up after 1,000,000 steps 



Tim's regex   : "(?:\\.|[^\\"\n])*" 

"OK     : failed in 17 steps 

"This is a longer... : matched in 211 steps 

"This is another... : failed in 253 steps 


unrolled loop   : "[^\\"\n]*(?:\\.[^\\"\n]*)*" 

"OK     : failed in 5 steps 

"This is a longer... : matched in 5 steps 

"This is another... : failed in 5 steps 

затыкать, что в ваш код как дословная строка, вы получите:

Match m = Regex.Match(s, @"""[^\n""\\]*(?:\\.[^\n""\\]*)*"""); 

EDIT: Кстати, я не говорю вам нужно обязательно использовать это регулярное выражение, потому что это быстрее; другие решения почти наверняка достаточно быстры. Но если вам нужна максимальная производительность (при использовании regex), это, вероятно, способ ее достижения. То, что делает это настолько быстро, что регулярное выражение всегда движется вперед: никаких обратных ссылок, никаких обратных ссылок и, самое главное, никакого возврата.