[Baypiggies] More dramatic material?
K. Richard Pixley
rich at noir.com
Wed Feb 24 04:13:24 CET 2010
Regular expressions aren't particularly fast. That's not the reason for
using them. In fact, there was a sort of competition going back in the
80's with various types of grep's. Look up boyer-moore, (bgrep), and
the difference between egrep and fgrep. The bottom line is that for
certain kinds of expressions, different algorithms are more efficient.
But the more efficient algorithms trade robustness and problem domain
for speed. That is, they work faster, but only on a subset of cases.
On the others, they either don't work at all or silently produce
Similarly, LALR(0) languages are easier and faster to parse than
LALR(1). You don't really need a parser generator like yacc, bison, or
byacc if your language is LALR(0).
There's a related, but somewhat more subdued competition going on right
now about binary diff programs, which have many related properties. So
do compression programs and I think everyone's probably aware of that
long standing competition. And I'll only mention message digesting,
(aka, encryption), which also has similarities.
Anything done in C is faster than anything done in python, (assuming
competent implementations). The exceptions being things where "pure"
python is implemented in C anyway.
The win to regular expressions is not speed, but rather that they can
search for and find things that other types of searching can't, or can't
do easily. For "dramatic" examples, try searching for palindromes, or
repeated phrases like 'moinmoin' or 'wikiwiki', or sequences of double
repeating characters like vaccuum.
More information about the Baypiggies