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
1
I had a third attempt at porting difftastic from Dijkstra to A*, and I've eventually concluded that A* just isn't worth it for the implementation complexity.
I had fun writing it up though, and I've even attempted ASCII art for building intuitions:
3
I've been impressed with code written by Fable in my testing:
Difftastic: found small optimisations in a hot loop I'd already profiled extensively. Helped me prototype Dijkstra to A* too (hard to find a good heuristic).
Garden: Found some real bugs in my simplistic typechecker.
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.
