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

Question

Рассмотрим регулярное выражение

^(?:\s*(?:[\%\#].*)?\n)*\s*function\s 

Он предназначен, чтобы соответствовать октава/MATLAB файлы сценариев, которые начинаются с определения функции.

Однако выполнение этого регулярного выражения невероятно медленно, и я не совсем уверен, почему. Например, если я пытаюсь оценить его в Python,

>>> import re, time 
>>> r = re.compile(r"^(?:\s*(?:[\%\#].*)?\n)*\s*function\s") 
>>> t0=time.time(); r.match("\n"*15); print(time.time()-t0) 
0.0178489685059 
>>> t0=time.time(); r.match("\n"*20); print(time.time()-t0) 
0.532235860825 
>>> t0=time.time(); r.match("\n"*25); print(time.time()-t0) 
17.1298530102 

В английском языке, что последняя строка говорит, что мое регулярное выражение занимает 17 секунд, чтобы оценить по простой строки, содержащей 25 символов новой строки!

Что это за мое регулярное выражение, которое делает его настолько медленным, и что я могу сделать, чтобы исправить его?

---

EDIT: Для уточнения, я хотел бы мое регулярное выражение, чтобы соответствовать следующей строке, содержащим комментарии:

# Hello world 
function abc 

включая любое количество пробелов, но не

x = 10 
function abc 

потому что то строка не начинается с «функции». Обратите внимание, что комментарии могут начинаться с «%» или «#».

Answer 1

Замените \s на [\t\f ], чтобы они не уловили символы перевода строки. Это должно делаться только всей группой, не снимающей захват (?:[\t\f ]*(?:[\%\#].*)?\n).
Проблема в том, что у вас есть три жадных потребителя, которые соответствуют '\n' (\s*, (...\n)* и снова \s*).
В вашем последнем примере синхронизации, они будут пытаться все строки a, b и c (один для каждого потребителя), которые составляют 25*'\n' или любую подстроку d она начинается с, скажем e является то, что игнорируется, то d+e == 25*'\n'.
Теперь найдите все комбинации a, b, c и e так, чтобы a+b+c+e == d+e == 25*'\n' рассматривая также пустую строку для одной или нескольких переменных. Мне уже слишком поздно делать математику, но я уверен, что число огромно: D

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

Answer 2

Для ускорения вы можете использовать это регулярное выражение:

p = re.compile(r"^\s*function\s", re.MULTILINE) 

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