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, ...)

Graph comparing efficiencies in regular expression matching in Perl, Python, Ruby, awk, grep, tcl, and others

"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