Python 的 re 库运行 re.search 或者 re.match 的时间复杂度是大概是多少？

[zhoudaiyu]

有个后台任务要与 2500 个左右正则做匹配，再加上查三次库要接近 40s 才能完成，感觉正则匹配非常慢。

[dsg001]

不预编译？

[zhoudaiyu]

@dsg001 没有做

[Vegetable]

python 的算法和其他语言没什么太大区别，但是好的正则和坏的正则有天壤之别。
复杂度是可以做到 O(N)的吧，这个我不太确定。

[ClericPy]

不提 NFA DFA 什么的... 你这复杂度明显还是看自己表达式写的问题吧, 有些语法复杂度确实格外大开销就大...

至于要做 2500 次正则, 这需求层面没有可以优化的了么, 如果是匹配关键词走 AC 自动机更快点; 如果是匹配 url 可以先按 host 做好 map; 其他需求也有其他的解耦

至于前面的说提前 compile, 之前倒是看到 Python 的 re 是有缓存的, 是否预编译差距不该这么大, 打上 log 看看是不是查库那边的 IO 开销

[zhoudaiyu]

@ClericPy 查库很快的 2s 就够