Message54412
Logged In: YES
user_id=313935
"easy and fast" was the python solution for min-heaps, you
mean. Their API is sufficient for a few-line iterator
implementation. The possible solutions for max-heaps are
comparatively ugly and generally less efficient, the best
ways being either a custom per-case solution
(decorate-useheap-undecorate) or a generic indirection
through an item wrapper class that mirrors the __le__
operator with the additional overhead of python's method
call infrastructure.
I don't think max-heaps are less common than min-heaps in
any way. It just doesn't show that well since custom
solutions are easy to write most of the time (each and every
time).
The major issue with the current heapq implementation is the
design choice of not making it a class. I agree that it is a
major advantage to have it operate on generic lists, but it
come at the price of preventing easy integration of keyword
arguments as in sort() and sorted(). A usage like
h = heap(myIterator, reverse=true)
for item in h: print item
would be so handy...
For the use-cases: As I said before, nsmallest/nlargest are
enough in many cases, but they actually handle a very
special case where n is known. On the other hand, iterators
have become a major first-level construct for Python and I
consider iteration over the ordered elements of a heap a
very comon use case. The step towards an augmented API that
provides efficient iterators both for min-heaps and
max-heaps would both underline Python's paradigm shift and
considerably simplify code that currently suffers from
custom solutions.
And again: most of the code is already there.
Another possible solution: what about a module function
heapified(seq_or_iter, key=..., cmp=..., reverse=...)
in the style of sorted() but returning an iterator?
Advantage over sorted() being the higher efficiency if the
iterator is thrown away after a small number of calls.
Just an idea... |
|
Date |
User |
Action |
Args |
2007-08-23 16:10:36 | admin | link | issue1158313 messages |
2007-08-23 16:10:36 | admin | create | |
|