有工具可以把正则简化(如下面的r2
简单成r1
)的吗?或者re.compile
会简化正则表达式(结果看起来不会)吗?
# -*- coding: utf-8 -*-
import itertools
import re
string = "".join(map(str, range(1000000)))
r1 = r"[13579]{3}"
r2 = rf'{"|".join(map("".join, itertools.product("13579", repeat=3)))}'
r1 = re.compile(r1)
r2 = re.compile(r2)
match1 = re.findall(r1, string)
match2 = re.findall(r2, string)
assert sorted(match1) == sorted(match2)
结果:
In [78]: %timeit re.findall(r1, string)
167 ms ± 520 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
In [79]: %timeit re.findall(r2, string)
1.08 s ± 2.69 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
1
f6x 2020-12-18 12:53:13 +08:00
这个 r2 写的真牛
|
3
abersheeran 2020-12-18 14:45:54 +08:00
mark……如果真的有,给我也说一声。
|
4
geelaw 2020-12-18 14:56:14 +08:00 via iPhone 2
很可惜正则表达式最小化问题是 PSPACE-complete,所以不应该期待高效算法。
另外,最小化 NFA 也是 PSPACE-complete,而最小化 DFA 则是多项式时间可解的。然而从正则表达式算出最小 DFA 的意义也不是很大,除非是做编译器的 lexer——从正则表达式到 DFA,规模可以以指数级增长,只有精心设计的正则语言才适合用 DFA 表示。 |
5
Lemeng 2020-12-18 16:20:24 +08:00
有,就太好了
|