Могу ли я улучшить производительность этого регулярного выражения далее

Question

Я пытаюсь получить имена потоков из файла дампов потоков. Имена потоков обычно содержатся в «двойных кавычках» в первой строке каждого дампа потока. Это может выглядеть просто следующим образом:

"THREAD1" daemon prio=10 tid=0x00007ff6a8007000 nid=0xd4b6 runnable [0x00007ff7f8aa0000] 

Или же большой, как следует:

"[STANDBY] ExecuteThread: '43' for queue: 'weblogic.kernel.Default (self-tuning)'" daemon prio=10 tid=0x00007ff71803a000 nid=0xd3e7 in Object.wait() [0x00007ff7f8ae1000] 

Регулярное выражение, которое я написал просто один: "(.*)". Он захватывает все внутри двойных кавычек как группу. Однако это приводит к тяжелому возврату, что требует много шагов, как можно видеть here. Устно мы можем объяснить это регулярное выражение, как «захватить все, что заключена в двойные кавычки, как группа»

Так что я придумал другой регулярное выражение, которое выполняет то же самое: "([^\"])". Вербально мы можем описать это регулярное выражение как «захватить любое количество символов без двойной кавычки, которые заключены внутри двойных кавычек». Я не нашел никакого быстрого регулярного выражения, чем это. Он не выполняет никакого возврата и, следовательно, требует минимальных шагов, как можно видеть here.

Я сказал это выше моему коллеге. Он придумал еще один: "(.*?)". Я не понял, как это работает. Он выполняет значительно меньший откат, чем первый, но немного медленнее второго, как можно видеть here. Однако

• Я не понимаю, почему обратный путь останавливается раньше.
• Я понимаю, что ? является квантификатором, что означает . Однако я не понимаю, как используется здесь.
• На самом деле я не могу угадать, как мы можем описать это регулярное выражение в устной форме.

Мой коллега попытался объяснить мне, но я до сих пор не могу его полностью понять. Может ли кто-нибудь объяснить?

Answer 1

Краткое объяснение и решение

"(.*)" регулярное выражение включает в себя много возвратов, потому что он находит первый ", а затем захватывает всю строку и откатывается ищет ", который находится ближе к концу строки. Поскольку у вас есть цитировали подстроки ближе к началу, есть больше, чем возвраты с "(.*?)" как это ленивого квантор *? делает вид регулярные выражений для ближайшего " после первого " найден.

Отрицаемого символьного класс решение "([^"]*)" является лучшим из 3, потому что он не имеет, чтобы захватить все , только все, кроме " символов. Однако, чтобы остановить какой-либо откат и сделать выражение в конечном счете эффективным, вы можете использовать притяжательные кванторы.

Если вам нужно соответствовать строки как " + no quotes here + ", используйте

"([^"]*+)" 

или даже вам не нужно, чтобы соответствовать косую цитаты в этой ситуации:

"([^"]*+) 

См regex demo

Фактически я не могу Угадайте, как мы можем описать это регулярное выражение в устной форме.

Последнее "([^"]*+) регулярное выражение может быть описана как

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

Кванторы

Более подробную информацию о quantifiers from Rexegg.com:

A* Ноль или более, как, как можно больше (жадный), отказавшись от символов, если двигатель должен возвращаться назад (послушный)
A*? Нуль или больше Как нужно, чтобы разрешить общий шаблон (ленивый)
A*+ Нуль или больше Как можно больше (жадный), не отказываясь от символов, если engi ne пытается отступить (притяжательный)

Как вы видите, ? не является отдельным квантором, он является частью другого квантификатора.

Советуем узнать больше о том, почему Lazy Quantifiers are Expensive и что Negated Class Solution действительно безопасно и быстро справляется со своей строкой ввода (где вы просто соглашаетесь с цитатой, за которой следуют не кавычки, а затем окончательная цитата).

Разница между .*?, .* и [^"]*+ кванторы

• Жадный "(.*)" решение работает следующим образом: проверяет каждый символ слева направо, ища ", и однажды нашел Хватает всю строку до конца и проверяет каждый символ, если он равен ". Таким образом, в вашей входной строке она возвращается 160 раз.

• Ленивый "(.*?)" решение работает следующим образом: двигатель находит первое ", а затем переходит в шаблоне и пробует следующий маркер (который является ") против T в THREAD1. Это терпит неудачу, поэтому двигатель отступает и позволяет .*? расширить свое соответствие на один элемент, чтобы он соответствовал T. И снова двигатель продвигается по шаблону. Теперь он пробует " против H в THREAD1. Это не удается, поэтому двигатель отступает и позволяет .*? развернуть и сопоставить H. The process then repeats itself—the engine advances, fails, backtracks, allows the lazy .*? to expand its match by one item, advances, fails and so on. For each character matched by the .*?, the engine has to backtrack. From a computing standpoint, this process of matching one item, advancing, failing, backtracking, expanding is "expensive".

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

• притяжательные решение квантора с инвертированным символьным классом "([^"]*+)" работает следующим образом: двигатель находит крайнее левое ", а затем захватывает все символы, которые не " до первого ". Отрицательный класс символов [^"]*+ жадно соответствует нулю или нескольким символам, которые не являются двойной цитатой. Поэтому мы гарантируем, что точка-звезда никогда не перепрыгнет через первый встреченный ". Это более прямой и эффективный способ сопоставления между некоторыми разделителями. Обратите внимание, что в этом решении мы можем полностью доверять *, который количественно определяет [^"]. Несмотря на то, что он жадный, нет никакого риска, что [^"] будет соответствовать слишком много, поскольку он является взаимоисключающим с ". Это contrast principle из руководства по стилю regex [see source].

Обратите внимание, что притяжательные квантор не позволяет регулярное выражение двигателя BackTrack в подвыражения, когда совпадают, символы между " становятся один жесткий блок, который не может быть «пересортировка» из-за каких-то «неудобства», с которыми встречались regex engine, и он не сможет сдвинуть любые символы из и в этот блок текста.

Для текущего выражения это не имеет большого значения.