[Python-Dev] Joys of Optimization

[Raymond Hettinger]

[Agthorr]
> Searching the research literature for a few hours, Pairing Heaps seem
> like the way to go.  They are very fast in practice, and their
> amortized asymptotic bounds are nearly as good as the Fibonacci Heap.
> The only difference is in the Decrease Key operation, where the
> Pairing Heaps bound is somewhere between Theta(log log n) and O(log
> n)--the tight bound is still an open research problem.
> 
> The interface to any high-performance heap would be the same, so it
> makes sense to implement a reasonably straightforward heap now.
> The implementation could always be changed to Fibonacci Heaps later if
> it turns out that there's a pressing need for everyone to have a heap
> implementation that has better performance when you're performing
> millions of Decrease Key operations...

That is reasonable.


> If there's rough concensus for this, I'd start by making a Python
> implementation, test code, and documentation.  Once that's done, I'd
> write the high-performance C implementation.

Along the way, either send me period code updates and I'll load them
into the sandbox.  That way, everyone can experiment with it and make
course corrections as necessary.


Raymond Hettinger