有个后台任务要与 2500 个左右正则做匹配，再加上查三次库要接近 40s 才能完成，感觉正则匹配非常慢。
Python 的 re 库运行 re.search 或者 re.match 的时间复杂度是大概是多少？
zhoudaiyu ·PRO
This topic created in 2242 days ago, the information mentioned may be changed or developed.
 |
1
dsg001 Apr 24, 2020
不预编译？
|
 |
3
Vegetable Apr 24, 2020
python 的算法和其他语言没什么太大区别，但是好的正则和坏的正则有天壤之别。
复杂度是可以做到 O(N)的吧，这个我不太确定。 |
 |
4
ClericPy Apr 24, 2020
不提 NFA DFA 什么的... 你这复杂度明显还是看自己表达式写的问题吧, 有些语法复杂度确实格外大开销就大...
至于要做 2500 次正则, 这需求层面没有可以优化的了么, 如果是匹配关键词走 AC 自动机更快点; 如果是匹配 url 可以先按 host 做好 map; 其他需求也有其他的解耦 至于前面的说提前 compile, 之前倒是看到 Python 的 re 是有缓存的, 是否预编译差距不该这么大, 打上 log 看看是不是查库那边的 IO 开销 |
Select Language