10 Aug
2006
10 Aug
'06
3:19 p.m.
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? Thanks, Jared. -- http://www.updike.org/~jared/ reverse ")-:"