[Python-Dev] Joys of Optimization (original) (raw)

Raymond Hettinger python at rcn.com
Sat Mar 20 12:14:51 EST 2004

[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

More information about the Python-Dev mailing list