[Python-Dev] Re: heaps (original) (raw)

Raymond Hettinger python@rcn.com
Sun, 4 May 2003 22:26:47 -0400

The relative speed (compared to the heapq code) varies under 2.3, seeming to depend mostly on M/N. The test case is set up to find the 1000 largest of a million random floats. In that case the sorting method takes about 3.4x longer than the heapq approach. As N gets closer to M, the sorting method eventually wins; when M and N are both a million, the sorting method is 10x faster. For most N-best apps, M is much smaller than N, and the heapq code should be quicker unless the data is already in order.

FWIW, there is C implementation of heapq at: http://zhar.net/projects/python/

Raymond Hettinger