可怜的Python're'performan

2024-03-28 14:05:05 发布

您现在位置:Python中文网/ 问答频道 /正文

我正在为autocompletion in lua使用的一个高级包使用Python的're'模块,但是有一个regex导致了严重的减速。下面是一个简单的例子:

import re
rx = re.compile(r"\bfunction(?:\s+[a-zA-Z0-9._]*)?\(((?:[a-zA-Z_][a-zA-Z0-9_]*|\.\.\.|,\s*)*)\)")
rx.match('function f(aaaaaaa, bbbbbbbb, cccccccc, ddddddd eeeeee)')  # Very slow
rx.match('function f(aaaaaaa, bbbbbbbb, cccccccc, ddddddd, eeeeee)')  # Adding a comma between the last function arguments in the string fixes it.

我对regex调试已经不了解了,但是this seems relevant,尽管这是我的头绪。你知道吗

有没有人知道我可以使用的等效模式,但哪种模式具有良好的性能?你知道吗

谢谢你!你知道吗


Tags: theinrematch模式functionrxregex
2条回答

主要问题来自嵌套的量词(?:[a-zA-Z_][a-zA-Z0-9_]*|\.\.\.|,\s*)*,当下面的子模式失败时,它可能会导致灾难性的回溯。你知道吗

如果展开此子模式,可以避免此问题。我使用了详细模式使其更具可读性:

re.compile(r'''\bfunction\b \s*[a-zA-Z0-9._]*
\(

(
  (?:
    (?:[a-zA-Z_][a-zA-Z0-9_]*|\.\.\.)
    (?: ,\s* (?:[a-zA-Z_][a-zA-Z0-9_]*|\.\.\.) )*
  )?
)

\)''', re.VERBOSE)

demo

(*):基本上是将(a*|b)*改为a*(ba*)*

问题是模式包含一个*量化的*量词:(?:[a-zA-Z_][a-zA-Z0-9_]*|\.\.\.|,\s*)*。必须避免使用这些嵌套的量词。如果你不能将备选方案重新安排到后面的(可选)组中,所有格量词或原子组通常会有所帮助。你知道吗

Pythonre不支持所有格量词,也不支持原子组。你知道吗

但是,可以使用具有模拟原子组的版本:

\bfunction(?:\s+[a-zA-Z0-9._]*)?\(((?:(?=([a-zA-Z_][a-zA-Z0-9_]*))\2|\.\.\.|,\s*)*)\)
                                      ^^^^^^^^^^^^^^^^^^^^^^^^^^^^                  

[a-zA-Z_][a-zA-Z0-9_]*子模式被放置到一个捕获组中,该捕获组被一个正的lookback包围。(?=([a-zA-Z_][a-zA-Z0-9_]*))\2几乎等同于[a-zA-Z_][a-zA-Z0-9_]*(因为它匹配相同的内容),但它使子模式原子化(因此,在其他方面它看起来像[a-zA-Z_][a-zA-Z0-9_]*+(?>[a-zA-Z_][a-zA-Z0-9_]*+))。\2回溯引用的“原子”性质不会让回溯超出[a-zA-Z_][a-zA-Z0-9_]*。你知道吗

参见regex demo。你知道吗

另外,您可能需要re.search,因为您的模式以\b开头。请注意,re.match只能在字符串的开头找到匹配项(=它被锚定在字符串的开头)。你知道吗

相关问题 更多 >