3 ms·
But it's not a trivial speed increase -- for some cases PCREs are O(2^n) where Thomson's NFA is at worst O(n^2). The Thomson NFA quickly gets to be millions of
by blasdel 17y ago
But it's not a trivial speed increase -- for some cases PCREs are O(2^n) where Thomson's NFA is at worst O(n^2). The Thomson NFA quickly gets to be millions of times faster
Thomson's algorithm would let you could use regular expressions for cases where you would otherwise have never tried.
- haberman 17y ago> The Thomson NFA quickly gets to be millions of times faster The O(2^n) worst case only comes from highly ambiguous patterns which are better written in other ways. So this isn't really accurate in practice.
- steveklabnik 17y agoYes, a 1u to .1u increase is 10x, but it's still trivial. In most cases, everything else that you're doing is much slower than the match. Yes, in a degenerate case, the PCRE performs abysmally, but seriously, are you ever going to use "a?a?a?aaa"? I'd like to see some numbers on the average, not the absolute worst case.