2 ms·
Priority queues aren't constant time. They're log time.
by EnderShadow8 5y ago
Priority queues aren't constant time. They're log time.
- extropy 5y agoFibonacci queue is a bit special that insertion is constant but extraction is log. A-star is very insertion heavy. In easy cases with a factor of 5, so using Fib gives significant boost in performance.
- siraben 5y agoIntMaps in Haskell actually have time complexity of O(min(n,W))[0] = O(1) for this problem, for insertion and getting the minimal element where n is the number of entries in the map (which is 9 here) and W is the word size in bits. Another way to think of it is it's just a fixed-length array where the entries are lists of vertices. [0] https://hackage.haskell.org/package/containers-0.6.5.1/docs/Data-IntMap-Strict.html https://hackage.haskell.org/package/containers-0.6.5.1/docs/...
- yxhuvud 5y agoYes, though sometimes it is possible to replace a fully general priority queue with a faster structure that is using the structure of the problem at hand. For example, this problem (AoC day 15) has only ever a count of unique priorities that is 11 or fewer. That allows a queue implementation to be https://github.com/yxhuvud/aoc21/blob/main/day15.cr#L27-L51 https://github.com/yxhuvud/aoc21/blob/main/day15.cr#L27-L51 , being amortized O(1) in both insertion and deletion. This pushed down the runtime another magnitude for me, the whole day running at 0.014s.