17th September 2003
Via Ned Batchelder, an article on Reversing Regular Expressions from Perl.com. Otherwise known as Sexeger, these offer a performance boost over normal regular expressions for certain tasks. The basic idea is pretty simple: searching backwards through a string using a regular expression can be a messy business, but by reversing both the string and the expression, running it, then reversing the result far better performance can be achieved (reversing a string is a relatively inexpensive operation). The example code is in Perl, but I couldn’t resist trying it in Python. The challenge is to find the last number occurring in a string.
>>> import re >>> lastnum = re.compile(r'(\d+)(?!\D*\d)') >>> s = ' this isa 454 asd very very very long strin9 asd9 009 76 with numbers 99 in it and here is the last 537 number' # NB this was all on one line originally >>> lastnum.search(s).group(0) '537' >>> import timeit >>> t1 = timeit.Timer('lastnum.search(s).group(0)', 'from __main__ import lastnum, s') >>> print "%.2f usec/pass" % (1000000 * t1.timeit(number=100000)/100000) 26.82 usec/pass >>> lastnumrev = re.compile('(\d+)') >>> lastnumrev.search(s[::-1]).group(0)[::-1] '537' >>> t2 = timeit.Timer('lastnumrev.search(s[::-1]).group(0)[::-1]', 'from __main__ import lastnumrev, s') >>> print "%.2f usec/pass" % (1000000 * t2.timeit(number=100000)/100000) 9.26 usec/pass
There are a few points worth explaining in the above code. The
(?!\D*\d) part of the first regular expression is a negative lookahead assertion—it basically means "match the subpattern provided it isn’t followed by a string of non-digits followed by at least one digit. This is the bit that ensures we only get back the last digit in the string, and is also the bit that could cause a performance problem.
'some string'[::-1] is an example of Extended Slices, introduced in Python 2.3. Its affect is to reverse the string, by stepping through it from start to end going back one character at a time.
The resutls speak for themselves: 26.82 for the lookahead assertion expression compared to just 9.26 for the reversed regular expression. This is definitely a useful trick to add to the tool box.
More recent articles
- Prompt injection explained, November 2023 edition - 27th November 2023
- I'm on the Newsroom Robots podcast, with thoughts on the OpenAI board - 25th November 2023
- Weeknotes: DevDay, GitHub Universe, OpenAI chaos - 22nd November 2023
- Deciphering clues in a news article to understand how it was reported - 22nd November 2023
- Exploring GPTs: ChatGPT in a trench coat? - 15th November 2023
- Financial sustainability for open source projects at GitHub Universe - 10th November 2023
- ospeak: a CLI tool for speaking text in the terminal via OpenAI - 7th November 2023
- DALL-E 3, GPT4All, PMTiles, sqlite-migrate, datasette-edit-schema - 30th October 2023
- Now add a walrus: Prompt engineering in DALL-E 3 - 26th October 2023
- Execute Jina embeddings with a CLI using llm-embed-jina - 26th October 2023