Re: diff in Haskell: clarification
there is the perl version of the diff algorithm on CPAN that may be a better starting point than the C version. -- Yoann Padioleau, INSA de Rennes, France, Opinions expressed here are only mine. Je n'écris qu'à titre personnel. **____ Get Free. Be Smart. Simply use Linux and Free Software. ____**
Yoann Padioleau wrote:
there is the perl version of the diff algorithm on CPAN that may be a better starting point than the C version.
I think in fact I'm going to give up on stealing other people's code and write my own version from Myer's paper. George
You caught my attention. It would be nice if you write your own version from scratch to make all of us profit of this. Thank you. Francis Girard Le Conquet France Le 22 Novembre 2002 16:03, George Russell a écrit :
I think in fact I'm going to give up on stealing other people's code and write my own version from Myer's paper.
George _______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
Francis Girard wrote:
You caught my attention.
It would be nice if you write your own version from scratch to make all of us profit of this.
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.
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. Cheers, Andrew Bromage
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.
participants (4)
-
Andrew J Bromage -
Francis Girard -
George Russell -
Yoann Padioleau