Interval Heap vs MinHeap

Jump to navigation Jump to search

How about keeping a flag in your leaf node processing so that you only try pruning if you added a new item?

Skilgannon (talk)15:48, 20 July 2013

Just tried that. The pruning is still not paying off compared to the extra overhead of the IntervalHeap.

Rednaxela (talk)16:05, 20 July 2013

And how about if you just use the IntervalHeap, but don't try any pruning? I'm curious whether the pruning is slow, or the different heap.

Skilgannon (talk)16:26, 20 July 2013

I was thinking it was the different heap... but actually turns out the heaps are approximately the same performance, with the difference being the pruning:

 - #1 Rednaxela's kd-tree (3rd gen, Interval Heap) [0.0290]
 - #2 Rednaxela's kd-tree (3rd gen) [0.0290]
 - #3 Rednaxela's kd-tree (3rd gen, Interval Heap, Prune When Points Added) [0.0293]
 - #4 Rednaxela's kd-tree (3rd gen, Interval Heap, Avoid Growing Heap When Possible) [0.0294]
 - #5 Skilgannon's Cache-hit KDTree [0.0296]
Rednaxela (talk)17:26, 20 July 2013

So the incremental difference from a larger heap is less than the cost of removing the points.

Skilgannon (talk)20:54, 20 July 2013