Spent some time today trying to replace difftastic's implementation of Dijkstra's algorithm with A* search.
I got a working implementation that passes tests: https://github.com/Wilfred/difftastic/commit/9a271169f68cdb678efe2035f5a4e45daeb6533d but sadly it's no faster. My slowest files still take 1.5 seconds with similar memory.
miniblog.
Related Posts
Today I learnt that A* doesn't work for an arbitrary non-planar graph, you need additional structure:
https://stackoverflow.com/q/26568552/509706
This matches my experience with difftastic so far. The graph is non-planar and my best heuristic only matches Dijkstra perf in typical cases.
I've started playing again with A* search instead of Dijkstra for difftastic. So far it's only saved me visiting 3% of graph nodes, which is negligible.
A* works best when you have a good heuristic, but finding a good heuristic is hard. Currently:
Today I learnt about radix heaps! They're a faster min-heap when your values are monotonically increasing -- perfect for Dijkstra. It saved 15% runtime for difftastic :)
Wikipedia reference: https://en.wikipedia.org/wiki/Radix_heap
The library I'm using: