我正在为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,尽管这是我的头绪。你知道吗
有没有人知道我可以使用的等效模式,但哪种模式具有良好的性能?你知道吗
谢谢你!你知道吗
主要问题来自嵌套的量词
(?:[a-zA-Z_][a-zA-Z0-9_]*|\.\.\.|,\s*)*
,当下面的子模式失败时,它可能会导致灾难性的回溯。你知道吗如果展开此子模式,可以避免此问题。我使用了详细模式使其更具可读性:
demo
(*):基本上是将
(a*|b)*
改为a*(ba*)*
问题是模式包含一个
*
量化的*
量词:(?:[a-zA-Z_][a-zA-Z0-9_]*|\.\.\.|,\s*)*
。必须避免使用这些嵌套的量词。如果你不能将备选方案重新安排到后面的(可选)组中,所有格量词或原子组通常会有所帮助。你知道吗Python
re
不支持所有格量词,也不支持原子组。你知道吗但是,可以使用具有模拟原子组的版本:
[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
只能在字符串的开头找到匹配项(=它被锚定在字符串的开头)。你知道吗相关问题 更多 >
编程相关推荐