Software

As a computer scientist, I occasionally write software. Some things that I have written in my spare time get posted here.

• A Fibonacci heap for Python

  This is a C extension to Python providing a priority queue implemented as a Fibonacci heap, which allows decrease-key operations in amortized constant time. (Python's heapq module is a poor solution for any priority queue that requires the ability to decrease keys on existing heap entries -- as in, for instance, an A* search. It is necessary, using heapq, to re-heapify the entire list, a linear-time operation.)

  This software could generously be described as "alpha", since error-checking is minimal, functionality is limited, and I have had no opportunity to perform extensive testing on it; however, an A* search over approximately 360,000 nodes runs twenty seconds faster on my MacBook Pro using the Fibonacci heap than a heapq list. Comparable results are obtained on Linux workstations. I have run searches with this extension and verified its basic functionality on Mac OS X 10.5 with Python 2.6, and on RedHat Linux with Python 2.5 and 2.6. I have not tested it on Windows or with Python 3.0; if anyone does so, I would appreciate knowing the results.

  This software may be used under the MIT license; it is freely usable for any purpose, commercial or non-commercial, open or closed. If you discover bugs or have bugfixes or improvements, I encourage you to contact me and let me know about them.

  Download distutils source packages for *nix/Mac OS X or Windows.

• PyCorpcor

  This is a translation of large parts of the R package corpcor into a pure-Python implementation. It is useful for situations where you need to estimate a covariance or precision matrix but have fewer observations than features, and uses a shrinkage approach to the estimation. Its major advantage over the original R package combined with R and RPy is portability to systems that don't have RPy.

  The software is beta -- it passes basic comparison tests to the output of the original R package but I have by no means stressed it for correctness. The software may contain bugs as well, though I am unaware of any.

  This software requires Python 2.6 or greater and Scipy 0.7 or greater, and is licensed under GNU GPL v3.

  You can download a gzipped tarball of the Python source and some sample data.