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