V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
推荐学习书目
Learn Python the Hard Way
Python Sites
PyPI - Python Package Index
http://diveintopython.org/toc/index.html
Pocoo
值得关注的项目
PyPy
Celery
Jinja2
Read the Docs
gevent
pyenv
virtualenv
Stackless Python
Beautiful Soup
结巴中文分词
Green Unicorn
Sentry
Shovel
Pyflakes
pytest
Python 编程
pep8 Checker
Styles
PEP 8
Google Python Style Guide
Code Style from The Hitchhiker's Guide
ispinfx
V2EX  ›  Python

正则表达式的简化?

  •  
  •   ispinfx · 2020-12-18 12:34:44 +08:00 · 2226 次点击
    这是一个创建于 1426 天前的主题,其中的信息可能已经有所发展或是发生改变。

    有工具可以把正则简化(如下面的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)
    
    5 条回复    2020-12-18 16:20:24 +08:00
    f6x
        1
    f6x  
       2020-12-18 12:53:13 +08:00
    这个 r2 写的真牛
    ispinfx
        2
    ispinfx  
    OP
       2020-12-18 13:18:38 +08:00
    @f6x 只是一个例子…
    abersheeran
        3
    abersheeran  
       2020-12-18 14:45:54 +08:00
    mark……如果真的有,给我也说一声。
    geelaw
        4
    geelaw  
       2020-12-18 14:56:14 +08:00 via iPhone   ❤️ 2
    很可惜正则表达式最小化问题是 PSPACE-complete,所以不应该期待高效算法。

    另外,最小化 NFA 也是 PSPACE-complete,而最小化 DFA 则是多项式时间可解的。然而从正则表达式算出最小 DFA 的意义也不是很大,除非是做编译器的 lexer——从正则表达式到 DFA,规模可以以指数级增长,只有精心设计的正则语言才适合用 DFA 表示。
    Lemeng
        5
    Lemeng  
       2020-12-18 16:20:24 +08:00
    有,就太好了
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   5692 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 28ms · UTC 03:17 · PVG 11:17 · LAX 19:17 · JFK 22:17
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.