Fastest regular expression that does not match any string

python, regex

Solution

A single character is a valid regular expression. A single character that is not "magic" matches itself. If you can identify a single character that will never, ever appear in your text, you could make a pattern from that.

How about ASCII NUL, character 0?

I stuck in one more string in your test program, the string: `'\0'`

It was about as fast as your best pattern: `b(?<!b)`

Okay, you already have a character after the end of the string. How about a character before the start of the string? That's impossible: `'x^'`

Aha! That's faster than checking for a character after end of string. But it's about as fast as your best pattern.

I suggest replacing the `b` with an ASCII NUL and calling it good. When I tried that pattern: `\0(?<!\0)`

It wins by a tiny fraction. But really, on my computer, all the ones discussed above are so close together that there isn't much to distinguish them.

Results:

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

That was fun. Thanks for posting the question.

EDIT: Ah hah! I rewrote the program to test with real input data, and got a different result.

I downloaded "The Complete Works of William Shakespeare" from Project Gutenberg as a text file. (Weird, it gave an error on `wget` but let my browser get it... some sort of measure to protect against automated copying?) URL: http://www.gutenberg.org/cache/epub/100/pg100.txt

Here are the results, followed by the modified program as I ran it.

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

So yeah I'm definitely going with that first one.

#!/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))

Problem

Original source