3 ms·
Nice work on your visualization! Thank you for rebutting the Fraser article; I came to the same conclusion as you (that Myers algorithm is in fact correct) but
by ridiculous_fish 7y ago
Nice work on your visualization! Thank you for rebutting the Fraser article; I came to the same conclusion as you (that Myers algorithm is in fact correct) but had never written it up.
I wrote a vectorized Myers implementation for diffing binary files. Perhaps the most interesting aspect is the progress bar: it's not obvious how to create a monotonic progress estimate for Myers diff.
https://github.com/ridiculousfish/HexFiend/blob/master/framework/sources/HFByteArrayEditScript.m https://github.com/ridiculousfish/HexFiend/blob/master/frame...
- robertelder 7y agoCool. You've got a fairly impressive following on that tool. I wish more people took an interest in studying these sorts of algorithms. Most people assume that some genius figured out the optimal way to do things years ago, but more often than not if you spent a few weeks focusing on a specific paper/algorithm, you'll come up with ideas for improvement (although it might not always be in the way you initially expected). Sometimes the improvement is just figuring out a better way to explain it and that in itself can lead other people to create breakthroughs. I think there are still a few improvements that could be done the the Myers algorithms. One specifically, is that I'm pretty sure it's tail recursive. You won't get any big O improvements off of that, but less stack space is still an improvement. Plus better cache locality. I'd work on some demos, but too many things to do these days...
- smrq 7y agoHey! You made the hex editor I use. Thanks! :)