Медленное выполнение регулярных выражений

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

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

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

Ответ 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);

Ответ 2

ИЗМЕНИТЬ

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

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

Значение:

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

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

Ответ 3

Try

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

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

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

Я использую 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

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

Ответ 4

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

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

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

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

Способ 2, чередование

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

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

информация

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

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

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

(?x-ism:" ( (?: \\?. )*? ) ")
код занял: 14.7031 secclock secs (14.58 usr + 0.00 sys = 14.58 CPU)

(?x-ism:" (.*? (?<!\\) (?:\\{2})* ) ")
код занял: 12.8435 secclock secs (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 secclock secs (8.75 usr + 0.00 sys = 8.75 CPU)

(?x-ism: " ( (?: \\. | [^"\\]+ )* ) " )
код занял: 8.5623 secclock secs (8.44 usr + 0.00 sys = 8.44 CPU)

(?x-ism: " ( [^"\\]* (?: \\. [^"\\]* )* ) " )
код занял: 7.79661 wallclock secs (7.80 usr + 0.00 sys = 7.80 CPU)

(?x-ism: (?> " ( (?: [^"\\] | \\. )* " ) ) )
код занял: 10.5156 secclock secs (10.52 usr + 0.00 sys = 10.52 CPU)

Ответ 5

Вот что я буду использовать:

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

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

Я использовал RegexBuddy для сравнения производительности вашего регулярного выражения, регулярного выражения Tim без привязок, и этого. Я поместил курсор перед началом цитаты в каждой из ваших строк примера и использовал "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 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), это, вероятно, способ ее достижения. То, что делает его настолько быстрым, что регулярное выражение всегда движется вперед: никаких обратных ссылок, никаких обратных ссылок и, самое главное, никакого возврата.