Python 的 re 库运行 re.search 或者 re.match 的时间复杂度是大概是多少？
zhoudaiyu · 2020-04-24 20:28:42 +08:00 via iPhone · 1471 次点击这是一个创建于 1672 天前的主题，其中的信息可能已经有所发展或是发生改变。
有个后台任务要与 2500 个左右正则做匹配，再加上查三次库要接近 40s 才能完成，感觉正则匹配非常慢。
 |
1
dsg001 2020-04-24 20:35:56 +08:00
不预编译？
|
 |
3
Vegetable 2020-04-24 20:43:27 +08:00
python 的算法和其他语言没什么太大区别，但是好的正则和坏的正则有天壤之别。
复杂度是可以做到 O(N)的吧，这个我不太确定。 |
 |
4
ClericPy 2020-04-24 20:52:53 +08:00
不提 NFA DFA 什么的... 你这复杂度明显还是看自己表达式写的问题吧, 有些语法复杂度确实格外大开销就大...
至于要做 2500 次正则, 这需求层面没有可以优化的了么, 如果是匹配关键词走 AC 自动机更快点; 如果是匹配 url 可以先按 host 做好 map; 其他需求也有其他的解耦 至于前面的说提前 compile, 之前倒是看到 Python 的 re 是有缓存的, 是否预编译差距不该这么大, 打上 log 看看是不是查库那边的 IO 开销 |
Select Language