[Python-Dev] Joys of Optimization

[Agthorr]

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