[Haskell-cafe] Knuth Morris Pratt for Lazy Bytestrings implementation

[Tim Docker]

Now I wonder what that 7MB file might be? :-)

We (team TNT) implemented KMP over lazy bytestrings as part of our icfp
2007 contest entry. As I remember, for the DNA evaluator it gave modest
speed improvements over more naïve searching. Our implementation was based
upon this blog post:

    http://twan.home.fmf.nl/blog/

Tim

> I've implemented KMP string searching for lazy bytestrings, and I'd
> like some help improving the performance of the code. I'd also like to
> know if it doesn't look correct - I've tested it pretty extensively
> but you never know ...
>
> I've been testing on a 7 MB file, where the search sequence is not
> found. Using strict byestrings, lazy bytestrings, and regular strings,
> I've found my algorithm is about twice as slow as the strict version.
> Surprisingly, the strict version is a little bit *slower* than the
> regular strings version.
>
> Thanks for any comments or help!
>
> Justin
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>