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

Agthorr agthorr at barsoom.org
Sat Mar 20 02:38:58 EST 2004

On Fri, Mar 19, 2004 at 12:21:33AM -0500, Raymond Hettinger wrote:

1) collections.heap(), a high performance Fibonacci heap implemented as a type and taking sort style arguments (cmp=, key=, reverse=).

I'd be willing to implement a high-performance heap, although I'd like to start a discussion about the right sort of heap to implement. Fibonacci heaps have good worst-case amortized behavior, but they are complicated to implement and have large hidden constants.

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...

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.

-- Dan Stutzbach

More information about the Python-Dev mailing list