Public Void - Programming Blog (Beta)
A programming blog covering C/C++, Java, Perl, PHP, Python, Ruby, Ruby on Rails, and UNIX/Linux shell scripting.
Sunday, March 18, 2007
Regular Expression Matching Can Be Simple And Fast
(but is slow in Java, Perl, PHP, Python, Ruby, ...)
"Some might argue that this test is unfair to the backtracking implementations, since it focuses on an uncommon corner case. This argument misses the point: given a choice between an implementation with a predictable, consistent, fast running time on all inputs or one that usually runs quickly but can take years of CPU time (or more) on some inputs, the decision should be easy."Russ Cox
This paper by Russ Cox is a very interesting discussion of efficiencies in regular expression matching.
(Vim has joined Google Summer of Code 2007, and one project idea is to increase the efficiency of Vim's syntax highlighting and regular expression matching.)
Labels: google, lang:c, lang:perl, programming, regex, summer-of-code
3/18/2007 12:46:00 PM | Regular Expression Matching Can Be Simple And Fast
The Vim Google Summer of Code project has code for download.