[Haskell-cafe] major speed improvement: regex-tdfa reaches 1.0.0
Martijn van Steenbergen
martijn at van.steenbergen.nl
Mon Mar 2 02:52:41 EST 2009
> The previous versions allowed bad combinations of pattern and searched
> text length to scale badly in the length of the text. Previously the
> worst case for text of length N was O(N^3).
> The new worst case asymptotic runtime scaled as O(N).
> There is never any backtracking.
> And the worst case storage space is independent of N.
That's an awesome result. :-) Thanks!
More information about the Haskell-Cafe