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:
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:
I've factored out the Vector and Edge definitions in difftastic so I can experiment with different graph search algorithms! It's so much easier when you can toggle between them.
So far A* is only 10% faster than Dijkstra, but I've found an additional 20% win that benefits all :)