最快的不匹配任何字符串的正则表达式
什么是最快的正则表达式，它不会匹配任何字符串？这听起来可能没什么用，但想象一下，有一个程序需要一个必需的正则表达式作为过滤器（这正是我遇到的情况）。我试过几种，发现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
更新：添加了一些建议的正则表达式的基准测试。
3 个回答
通常我们会使用简短方便的 (?!)，这个写法会直接失败。
如果你想要更明确一点，Perl/PCRE 里有 (*FAIL) 或 (*F) 这样的写法可以使用。
这可能不是你想要的那种答案，但我试了几分钟，得到的最好结果是这样的：'a{%d}' % (len(input)+1)。换句话说，就是计算你的模式，使得它可以是任何字符，并且这个字符的数量要比已知字符串的长度多一个。当然，这个方法只有在你能访问输入字符串的情况下才有效。而且这个方法的表现也很不错；我把文本变量改成了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
一个单独的字符可以作为有效的正则表达式。一个不带“魔法”的单字符会匹配它自己。如果你能找到一个在你的文本中永远不会出现的字符，你就可以用它来创建一个模式。
比如说ASCII NUL，字符0呢？
我在你的测试程序中加了一个字符串，这个字符串是：'\0'
它的速度和你最好的模式：b(?<!b)差不多。
好吧，你已经在字符串的末尾有一个字符了。那么在字符串开始之前有一个字符呢？这不可能：'x^'
哈哈！这个比检查字符串末尾的字符要快。但速度和你最好的模式差不多。
我建议把b替换成ASCII 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下载时出错，但我的浏览器却能下载... 这可能是为了防止自动复制的某种措施？）网址：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))