31 Jan
2016
31 Jan
'16
8:37 a.m.
Dave Horsfall scripsit:
I'm still trying to get my around about how a
program such as "egrep"
which handles complex patterns can be faster than one that doesn't... It
seems to defeat all logic :-)
Actually, it just appears to be that way. Many egrep things like + and ?
are supported in grep too, you just have to enter them as \+ and \?, at
least now that we have Posix regular expressions. What egrep does not
support that grep does is backreferences, and that allows it to use highly
efficient deterministic (i.e. non-backtracking) finite state automata.
Classic grep uses backtracking, which makes it much slower on problematic
expressions like "a*b" where there is no b in the input. On the other
hand, creating a deterministic automaton has higher setup costs.
--
John Cowan http://www.ccil.org/~cowan cowan(a)ccil.org
Si hoc legere scis, nimium eruditionis habes.