5

不匹配任何字符串的最快执行正则表达式是什么？这似乎是一件无用的事情，但考虑一个将强制正则表达式作为过滤器的程序（这实际上是我的场景）。我尝试了一些，并发现b(?<!b)它是表现最好的，因为它b很少出现在输入中。

这是我编写的用于测试不同模式的速度的python代码：

#!/usr/bin/env python

import re
import time

tests = [
  r'a\A',
  r'b\A',
  r'a^',
  r'b^',
  r'[^\s\S]',
  r'^(?<=a)',
  r'^(?<=b)',
  r'a(?<!a)',
  r'b(?<!b)',
  r'\Za',
  r'\Zb',
  r'$a',
  r'$b'
]
timing = []
text = 'a' * 50000000

for t in tests:
  pat = re.compile(t)
  start = time.time()
  pat.search(text)
  dur = time.time() - start
  timing.append((t, dur))

timing.sort(key=lambda x: x[1])
print('%-30s %s' % ('Pattern', 'Time'))
for t, dur in timing:
  print('%-30s %0.3f' % (t, dur))

在我的机器上，我得到以下时间：

Pattern                        Time
b(?<!b)                        0.043
b\A                            0.043
b^                             0.043
$a                             0.382
$b                             0.382
^(?<=a)                        0.395
\Za                            0.395
\Zb                            0.395
^(?<=b)                        0.414
a\A                            0.437
a^                             0.440
a(?<!a)                        0.796
[^\s\S]                        1.469

更新：为一些建议的正则表达式添加了基准。

4

3 回答 3

3

单个字符是有效的正则表达式。不是“魔术”的单个字符匹配自身。如果你能识别出一个永远不会出现在你的文本中的字符，你可以从中创建一个模式。

ASCII NUL，字符 0 怎么样？

我在您的测试程序中又插入了一个字符串，即字符串：'\0'

它与您的最佳模式一样快：b(?<!b)

好的，你已经在字符串末尾有了一个字符。字符串开头之前的一个字符怎么样？这不可能： 'x^'

啊哈！这比在字符串结束后检查字符要快。但它与您的最佳模式一样快。

我建议用bASCII NUL 替换它并称之为好。当我尝试这种模式时：\0(?<!\0)

它赢了一小部分。但实际上，在我的电脑上，上面讨论的所有这些都非常接近，以至于没有太多可以区分它们的地方。

结果：

Pattern                        Time
\0(?<!\0)                      0.098
\0                             0.099
x^                             0.099
b(?<!b)                        0.099
^(?<=x)                        1.416
$b                             1.446
$a                             1.447
\Za                            1.462
\Zb                            1.465
[^\s\S]                        2.280
a(?<!a)                        2.843

那很有趣。感谢您发布问题。

编辑：啊哈！我重写了程序以使用真实输入数据进行测试，得到了不同的结果。

我从古腾堡计划下载了“威廉莎士比亚全集”作为文本文件。（奇怪，它给出了一个错误wget但让我的浏览器得到它......某种防止自动复制的措施？） URL：http ://www.gutenberg.org/cache/epub/100/pg100.txt

这是结果，然后是我运行的修改后的程序。

Pattern                        Time
\0(?<!\0)                      0.110
\0                             0.118
x^                             0.119
b(?<!b)                        0.143
a(?<!a)                        0.275
^(?<=x)                        1.577
$b                             1.605
$a                             1.611
\Za                            1.634
\Zb                            1.634
[^\s\S]                        2.441

所以是的，我肯定会选择第一个。

#!/usr/bin/env python

import re
import time

tests = [
  r'x^',
  r'\0',
  r'[^\s\S]',
  r'^(?<=x)',
  r'a(?<!a)',
  r'b(?<!b)',
  r'\0(?<!\0)',
  r'\Za',
  r'\Zb',
  r'$a',
  r'$b'
]
timing = []
#text = 'a' * 50000000
text = open("/tmp/pg100.txt").read()
text = text * 10

for t in tests:
  pat = re.compile(t)
  start = time.time()
  pat.search(text)
  dur = time.time() - start
  timing.append((t, dur))

timing.sort(key=lambda x: x[1])
print('%-30s %s' % ('Pattern', 'Time'))
for t, dur in timing:
  print('%-30s %0.3f' % (t, dur))
于 2013-01-26T09:24:36.307 回答
0

这可能不是您正在寻找的那种答案，但我摆弄了几分钟，我能做的最好的事情就是：'a{%d}' % (len(input)+1). 或者，换句话说，将您的模式计算为最大量词长于 string 的已知长度的任何字符。这显然只有在您可以访问输入字符串时才有效。它似乎也可以很好地扩展。我把 texts 变量取出来texts = [os.urandom(20000) for x in range(20000)]，在那种情况下a{20001}仍然打卡在0.013.

但是，我还没有计算获取字符串长度和生成模式的操作成本，这显然是你必须在野外处理的。

更新脚本：

import os
import re
import time

tests = [
  r'\0(?<!\0)',
  r'\0',
  r'x^',
  r'a{2001}',
  r'a(?<!a)',
  r'b(?<!b)',
  r'\Za',
  r'\Zb',
  r'$a',
  r'$b'
]
texts = [os.urandom(2000) for x in range(20000)]
flag = 0

for t in tests:
    pat = re.compile(t)
    start = time.time()
    for text in texts:
        if pat.search(text):
            print('%-30s %10s' % (t, "FAILED"))
            flag = 1
            break
    if flag == 0:
        dur = time.time() - start
        print('%-30s %0.3f' % (t, dur))
    else:
        flag = 0

基准：

\0(?<!\0)                      0.058
\0                                 FAILED
x^                             0.055
a{2001}                        0.022
a(?<!a)                        0.060
b(?<!b)                        0.073
\Za                            0.798
\Zb                            0.797
$a                             0.757
$b                             0.767
于 2013-01-26T09:29:36.500 回答
0

(?!)通常我们使用直接失败的简短方便。

如果你想更明确 Perl/PCRE可以使用(*FAIL)or动词。(*F)

于 2013-01-26T09:57:49.147 回答