heapq "key" arguments
gagsl-py2 at yahoo.com.ar
Sat Aug 1 04:58:40 CEST 2009
En Fri, 31 Jul 2009 16:38:01 -0300, Joshua Bronson <jabronson at gmail.com>
> On Jul 31, 2:02 pm, Jonathan Gardner <jgard... at jonathangardner.net>
>> On Jul 31, 10:44 am, Joshua Bronson <jabron... at gmail.com> wrote:
>> > Say I want to maintain a heap of (x, y) pairs sorted only by
>> > first coordinate. Without being able to pass key=itemgetter(0), won't
>> > heapifying a list of such pairs unnecessarily compare both
>> > coordinates?
>> It will compare the second value only if the first values are equal.
> I don't see how that helps. That's not at all the same thing as being
> able to pass key=itemgetter(0).
Ok, it's not strictly the same, but usually it doesn't hurt. The heaqp
module doesn't promise anything about equal elements: it may keep the
original order, rearrange them at will, reverse them, whatever. So the
element-wise comparison of tuples is as good as comparing only the first
element - *except* when comparing the second element isn't cheap or has
side effects or something like that. In that case, use a custom class to
redefine comparison operators:
from heapq import heapify, heappop
"tuple that sorts only on first element"
def __lt__(self, other):
heap = [tuplebyfirst(x) for x in [(2, 3, 'A'), (1, 4, 'B'),
(2, 5, 'C'), (2, 5, 'D'), (3, 0, 'E')]]
[(2, 3, 'A'), (1, 4, 'B'), (2, 5, 'C'), (2, 5, 'D'), (3, 0, 'E')]
(1, 4, 'B')
(2, 5, 'C')
(2, 5, 'D')
(2, 3, 'A')
(3, 0, 'E')
The letters are just to recognize the original ordering.
(I've used an undocumented property: all heapq functions compare elements
ONLY by using "<", in 2.6.2 at least. Defining all the other rich
comparison methods doesn't change anything)
More information about the Python-list