Andrew J Bromage wrote: > > G'day all. > > On Mon, Nov 25, 2002 at 12:19:10PM +0100, George Russell wrote: > > > I have a confession to make. Andrew Bromage's list-based code is > > much faster than my array-based code. So I think I shall end up > > adapting Andrew Bromage's code, even though I do not understand it. > > You mean you did understand the Myers algorithm? :-) > > Let me know if you'd like a walk-through. It's actually pretty > straightforward once you've got the hang of it. > > For short jobs, such as finding the difference between two Haskell > identifier-sized words, O(N^2) algorithms almost always beat the > Myers O(ND) algorithm by sheer weight of constant factors. I'd > reserve more complex approaches for more complex data if I were you. What I find really *annoying* is that there doesn't seem to be a worst case subquadratic method when you are given a linear ordering as well. I mean there really ought to be one, but I don't see how you can do it even if all the two strings are allowed to contain is 0s and 1s. Perhaps I'm being really stupid somewhere.
I think more than a walk-through I would appreciate it if your code had some kind of fall-through to avoid it taking forever when someone throws it two completely different 10000 element lists. _______________________________________________ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
