Низкая производительность Regex

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

Вы столкнулись с катастрофическим возвратом:

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

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

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

Теперь для строки "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
• и т. Д.и т. д.

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

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

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

РЕДАКТИРОВАТЬ

Вот, пожалуйста: "\"([^\\\\\"]|\\\\.)*\""

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

Значение:

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

Не вкладывая свой *, вы не получаете экспоненциальный или бесконечный цикл, и он мгновенно возвращается для меня.

Answer 3

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

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

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

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

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

РЕДАКТИРОВАТЬ: Кстати, я не говорю, что вы должны использовать это регулярное выражение, потому что это быстрее;другие решения почти наверняка достаточно быстрые.Но если вам нужна максимальная производительность (хотя вы все еще используете регулярные выражения), это, вероятно, способ ее достижения.Что делает его таким быстрым, так это то, что регулярное выражение всегда движется вперед: никаких обратных ссылок, никаких обходных путей и, самое главное, никакого возврата назад.

Answer 4

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

Через различные тесты (включая мои собственные) это быстрые пути:

Способ 1, развертывание

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

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

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

Метод 1, может превзойти 2 по значительным запасам.

информация

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

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

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

(?x-ism:" ( (?: \\?. )*? ) ")
Код занял: 14,7031 сек. (с часами 14,58 грн. + 0,00 сис = 14,58 ед. ЦП)

(?x-ism:" (.*? (?<!\\) (?:\\{2})* ) ")
Код занял: 12,8435 сек. (с 12,75 грн. + 0,00 сис = 12,75 процессора)

(?x-ism:" ( (?: [^\\"] | \\. )* ) ")
Код занял: 10,3123 сек. (10,27 грн + 0,00 сис = 10,27 процессор)

(?x-ism: " ( (?: [^"\\]+ | (?:\\.)+ )* ) " )
Код занял: 8,39063 сек. (8,39 долл. США + 0,00 сис = 8,39 ЦП)

(?x-ism: " ( (?: [^"\\]+ | \\. )* ) " )
Код занял: 8,7498 сек. (8,75 долл. + 0,00 сис = 8,75 процессора)

(?x-ism: " ( (?: \\. | [^"\\]+ )* ) " )
Код занял: 8,5623 сек. (8,44 грн. + 0,00 сис = 8,44 ед. ЦП)

(?x-ism: " ( [^"\\]* (?: \\. [^"\\]* )* ) " )
Код занял: 7,79661 сек. (7,80 долл. США + 0,00 сис. = 7,80 ЦП)

(?x-ism: (?> " ( (?: [^"\\] | \\. )* " ) ) )
Код занял: 10,5156 сек. (10,52 грн. + 0,00 сис = 10,52 ед. ЦП)

Answer 5

Попробуйте

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

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