En Fri, 31 Jul 2009 16:38:01 -0300, Joshua Bronson <jabron...@gmail.com>
escribió:
On Jul 31, 2:02 pm, Jonathan Gardner <jgard...@jonathangardner.net>
wrote:
On Jul 31, 10:44 am, Joshua Bronson <jabron...@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
class tuplebyfirst(tuple):
"tuple that sorts only on first element"
def __lt__(self, other):
return self[0]<other[0]
heap = [tuplebyfirst(x) for x in [(2, 3, 'A'), (1, 4, 'B'),
(2, 5, 'C'), (2, 5, 'D'), (3, 0, 'E')]]
print heap
heapify(heap)
while heap:
print heappop(heap)
Output:
[(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)
--
Gabriel Genellina
--
http://mail.python.org/mailman/listinfo/python-list
