Ускорьте регулярное выражение

Question

Это регулярное выражение для извлечения имени таблицы из оператора SQL:

(?:\sFROM\s|\sINTO\s|\sNEXTVAL[\s\W]*|^UPDATE\s|\sJOIN\s)[\s`'"]*([\w\.-_]+)

Соответствует токену, необязательно заключенному в [`'"], с предшествующим FROM и т. Д., Окруженным пробелом, за исключением UPDATEкоторый не имеет ведущих пробелов.

Мы выполняем много регулярных выражений, и это самое медленное, и я не уверен почему.Строки SQL могут иметь размер до 4 КБ, а время выполнения составляет в худшем случае 0,35 мс на 2,2 ГГц i7 MBP.

Это медленный пример ввода: https://pastebin.com/DnamKDPf

Можем ли мысделать лучше?Разделение его на несколько регулярных выражений также будет возможным, если возникнут проблемы с чередованием.

Answer 1

Поскольку совпадения часто близки к концу, одной из возможностей будет, по сути, начать с конца и вернуться назад, а не начинать с начала и в прямом направлении, что-то вроде

^(?:UPDATE\s|.*(?:\s(?:(?:FROM|INTO|JOIN)\s|NEXTVAL[\s\W]*)))[\s`'\"]*([\w\.-_]+)

https://regex101.com/r/SO7M87/1/ (154 шага)

Хотя это может быть намного быстрее, когда есть совпадение, это лишь умеренное улучшение, когда нет совпадения, потому что шаблон должен полностью откатываться назадв начало ( ~ 9000 шагов от ~ 23k шагов)

Answer 2

Существует эмпирическое правило :

Не разрешайте движку пытаться сопоставить каждый отдельный символ, если есть некоторые границы.

Попробуйте следующее регулярное выражение (~ 2500 шагов для заданной входной строки):

(?!FROM|INTO|NEXTVAL|UPDATE|JOIN)\S*\s*|\w+\W*(\w[\w\.-]*)

Живая демоверсия

Примечание : Чтовам нужно находится в первой группе захвата.

Последнее регулярное выражение в соответствии с комментариями (что немного медленнее, чем в предыдущем чистом):

(?!(?:FROM|INTO|NEXTVAL|UPDATE|JOIN)\b)\S*\s*|\b(?:NEXTVAL\W*|\w+\s[\s`'"]*)([\[\]\w\.-]+)

Answer 3

Regex оптимизация - очень сложная тема, и ее следует выполнять с помощью некоторых инструментов.Например, мне нравится Regex101 , который вычисляет для нас количество шагов, которые Regex двигатель должен был сделать, чтобы соответствовать pattern - payload.Для вашего pattern и данного примера он печатает:

1 match, 22976 steps (~19ms)

Первое, что вы всегда можете сделать, это сгруппировать похожие детали в одну группу.Например, FROM, INTO и JOIN выглядят одинаково, поэтому мы можем написать регулярное выражение, как показано ниже:

(?:\s(?:FROM|INTO|JOIN)\s|\sNEXTVAL[\s\W]*|^UPDATE\s)[\s`'"]*([\w\.-_]+)

Для приведенного выше примера Regex101 , печать:

1 match, 15891 steps (~13ms)

Попробуйте найти некоторые онлайн-инструменты, которые объясняют и оптимизируют Regex, такие как myregextester и подсчитывают, сколько шагов нужно сделать движку.