[Python-Dev] heapq, min and max

[Kristján Valur Jónsson]

Hello there.
I was surprised to find recently that the heapq module is still a pure python implementation.
A few years ago we wrote our own in C for use in Eve-online, and we usually do a
import blue.heapq as heapq.
Having a python implementation of it almost completely negates any benefit of using that in place of sort() unles the comparison is really expensive.
I'd be happy to donate an implementation if there is any interest.

I also recently came across the recommendation that one should use the "min" and "max"  builtins instead of using heapq or sort() when trying to find
a single smallest element.
Well, this is also not true, for simple comparisons, because currently "min" and "max" use the iterator protocol, whereas sort() (and blue.heapq.heapify)
use direct list access, thus halving the number of python method calls approximately.

 s="""
import random
l = [random.random() for i in xrange(10000)]
"""
timeit.Timer("(l.sort(), l[-1])", s).timeit(1000)
0.29406761513791935
timeit.Timer("max(l)", s).timeit(1000)
0.4760155766743992
>>>

Now, this is easy enough to rectify, by providing a list specialization for min_max().  This would also make sure that "min" is truly the fastest
way to find the minimum member of a list.

Would there be interest in this?  (I will be patching the CCP version of python for it anyway).

We are using 2.5.3, but these changes should be directly applicable to 2.6 too.

K
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-dev/attachments/20081022/db27ea8f/attachment-0001.htm>