[Python-Dev] Joys of Optimization

[Hye-Shik Chang]

On Fri, Mar 19, 2004 at 11:38:58PM -0800, Agthorr wrote:
> 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.
> 
[snip]
> 
> 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.
> 

JFYI, I wrote a simple python wrapper[1] for a BSD-licensed fibonacci
library[2] about 2 years ago.  My wrapper implementation isn't good
enough to adopt it to collections module but it may be useful to
hack around for testing object interface and flow designs for our new
collections.heap().  :)

[1] http://people.linuxkorea.co.kr/~perky/fibheap-0.2.tar.gz
    (This wrapper package bundled C library source of [2].)
[2] http://resnet.uoregon.edu/~gurney_j/jmpc/fib.html

Cheers,
Hye-Shik