[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

ChrisK wrote:
> 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 mailing list