News for hackers. Stuff that matters.
Re:Ask HN: I just wrote an O(N) diffing algorithm – what am ... by ridiculous_fish on Monday October 28, 2019 @09:47PM (#21383607)
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/frame...

Re:Ask HN: I just wrote an O(N) diffing algorithm – what am ... by robertelder on Monday October 28, 2019 @10:54PM (#21383923)
Cool. 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...

Re:Ask HN: I just wrote an O(N) diffing algorithm – what am ... by smrq on Tuesday October 29, 2019 @03:08PM (#21390902)
Hey! You made the hex editor I use. Thanks! :)