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.