[Haskell-cafe] Re: Memoizing longest-common-subsequence
jupdike at gmail.com
Thu Aug 10 15:19:00 EDT 2006
> and also ended up with an STArray based implementation. I can send the
> code if you're interested. I have no idea how well it performs compared
> to Ian's, or the one in darcs (which uses PackedStrings).
Ian's LCS code looks like it works fine in terms of space usage, but
for large input (lengrh as == 40000, length bs == 50000) it seems to
be way too slow in terms of time complexity (GNU sdiff executes on
this same data in a few seconds, the Hunt-Szymanski LCS algorithm
didn't terminate, even after like 10 minutes).
If it's not too much trouble, could you send Myers STArray based code?
More information about the Haskell-Cafe