Kevin> I don't explicitly associate a priority with every item in the Kevin> queue - instead I rely on the user having a __cmp__ operator Kevin> defined on the items (if the default does not suffice). That's what I missed. >> Seems to me that you could implement the type of priority queue I'm >> think of rather easily using a class that wraps a list of Queue.Queue >> objects. Am I missing something obvious? Kevin> Perhaps I am, because I do not see how one would use Queue.Queue Kevin> efficiently for this task. I don't know how efficient it would be, but I usually think that most applications have a small, fixed set of possible priorities, like ("low", "medium", "high") or ("info", "warning", "error", "fatal"). In this sort of situation my initial inclination would be to implement a dict of Queue instances which corresponds to the fixed set of priorities, something like: import Queue class PriorityQueue: def __init__(self, priorities): self.queues = {} self.marker = Queue.Queue() self.priorities = priorities for p in priorities: self.queues[p] = Queue.Queue() def put(self, obj, priority): self.queues[priority].put(obj) self.marker.put(None) def get(self): dummy = self.marker.get() # at this point we know one of the queues has an entry for us for p in self.priorities: try: return self.queues[p].get_nowait() except Queue.Empty: pass if __name__ == "__main__": q = PriorityQueue(("low", "medium", "high")) q.put(12, "low") q.put(13, "high") q.put(14, "medium") print q.get() print q.get() print q.get() Obviously this won't work if your set of priorities isn't fixed at the outset, but I think it's pretty straightforward, and it should work in multithreaded applications. It will also work if for some reason you want to queue up objects for which __cmp__ doesn't make sense. Skip

On Tuesday 25 June 2002 06:09 am, Skip Montanaro wrote: ...

I don't know how efficient it would be, but I usually think that most applications have a small, fixed set of possible priorities, like ("low", "medium", "high") or ("info", "warning", "error", "fatal"). In this sort

Then you do "bin sorting", of course -- always worth considering when you know the sort key can only take a small number of different values (as is the more general "radix sorting" when you have a few such keys, or a key that easily breaks down that way). But it IS rather a special case, albeit an important one (and quite possibly frequently occurring in some application areas). Alex

Gustavo Niemeyer wrote:

If priority queues were to be included, I'd rather add the necessary support in Queue to easily attach priority handling, if that's not already possible.

it takes a whopping four lines of code, if you're a pragmatic programmer: # # implementation import Queue, bisect class PriorityQueue(Queue.Queue): def _put(self, item): bisect.insort(self.queue, item) # # usage queue = PriorityQueue(0) queue.put((2, "second")) queue.put((1, "first")) queue.put((3, "third")) priority, value = queue.get() </F>

Gustavo wrote:

def put(self, item, block=1, **kw): if block: self.fsema.acquire() elif not self.fsema.acquire(0): raise Full self.mutex.acquire() was_empty = self._empty() # <- Priority could be handled here as well. self._put(item, **kw) if was_empty: self.esema.release() if not self._full(): self.fsema.release() self.mutex.release()

def _put(self, item, **kw): # <- But here seems better priority = kw.get("priority", self.defaultpriority) bisect.insort(self.queue, (priority, item))

or better: def put(self, item, block=1, priority=None): if priority is None: priority = self.defaultpriority Queue.Queue.put(self, (priority, item), block) </F>

On Tue, Jun 25, 2002 at 09:23:43AM +0200, Martin v. Loewis wrote:

Oren Tirosh writes:

...

The only advantage of a heap is O(1) peek which doesn't seem so critical. It may also have somewhat better performance by a constant factor because it uses an array rather than allocating node structures. But the internal order of a heap-based priority queue is very non-intuitive and quite useless for other purposes while a sorted list is, umm..., sorted!

I think that heaps don't allocate additional memory is a valuable property, more valuable than the asymptotic complexity (which is also quite good). If you don't want to build priority queues, you can still use heaps to sort a list.

When I want to sort a list I just use .sort(). I don't care which algorithm is used. I don't care whether dictionaries are implemented using hash tables, some kind of tree structure or magic smoke. I just trust Python to use a reasonably efficient implementation. I always find it funny when C++ or Perl programmers refer to an associative array as a "hash".

IMO, heaps are so standard as an algorithm that they belong into the Python library, in some form. It is then the user's choice to use that algorithm or not.

Heaps are a "standard algorithm" only from a CS point of view. It doesn't have much to do with everyday programming. Let's put it this way: If Python has an extension module in the standard library implementing a sorted list, would you care enough about the specific binary heap implementation to go and write one or would you just use what you had in the library for a priority queue? ;-) Oren

On Tue, Jun 25, 2002, Martin v. Loewis wrote:

IMO, heaps are so standard as an algorithm that they belong into the Python library, in some form. It is then the user's choice to use that algorithm or not.

Should this PEP be split in two, then? One for a new "AbstractData" package (that would include the heap algorithm) and one for an update to Queue that would use some algorithm from AbstractData. The latter might not even need a PEP. -- Aahz (aahz@pythoncraft.com) <*> http://www.pythoncraft.com/ Project Vote Smart: http://www.vote-smart.org/

[Aahz]

Should this PEP be split in two, then? One for a new "AbstractData" package (that would include the heap algorithm) and one for an update to Queue that would use some algorithm from AbstractData. The latter might not even need a PEP.

I'm chuckling, but to myself <wink>. By the time you add all the bells and whistles everyone may want out of "a priority queue", the interface gets so frickin' complicated that almost everyone will ignore the library and call bisect.insort() themself. /F gives me a thread-safe Queue when I don't want to pay overheads for enforcing mutual exclusion in 99% of my priority-queue apps. Schemes that store (priority, object) tuples to exploit lexicographic comparison are convenient to code but a nightmare if priorities can ever be equal, and object comparison can raise exceptions, or object comparison can be expensive. Sometimes I want a min-queue, other times a max-queue. Sometimes I need efficient access to both ends. About a month ago I needed to write a priority queue that was especially efficient at adding thousands of new entries in one gulp. And so on. It's easier to write appropriate code from scratch in Python than to figure out how to *use* a package profligate enough to contain canned solutions for all common and reasonable use cases. People have been known to gripe at the number of methods Python's simple little lists and dicts have sprouted -- heh heh. BTW, the Zope BTree may be a good candidate to fold into Python. I'm not sure. It's a mountain of fairly sophisticated code with an interface so rich that it's genuinely hard to learn how to use it as intended -- the latter especially should appeal to just about everyone <wink>.

aahz> Fair enough -- but I didn't really know about bisect myself. aahz> Looking at the docs for bisect, it says that the code might be aahz> best used as a source code example. I always forget about it as well. I just added /F's four-line PriorityQueue class as an example in the bisect docs and a "seealso" pointing at the bisect doc to the Queue module doc. Skip

On Tue, Jun 25, 2002 at 02:52:03AM -0400, Oren Tirosh wrote:

...

Any chance something like this could make it into the standard python library? It would save a lot of time for lazy people like myself. :-)

A sorted list is a much more general-purpose data structure than a priority queue and can be used to implement a priority queue. It offers almost the same asymptotic performance:

Hi Oren, I agree that some form of a balanced tree object would be more useful, but unfortunately it doesn't exist natively. A pure python implementation of heaps is a pretty straight-forward addition. If, however, one were to consider adding C code then I would agree a tree object would be more valuable. As you surmised later, I wouldn't have bothered with a heap if trees were available. In fact, I've always wondered why Python dictionaries use the hash algorithm instead of the more general binary tree algorithm. :-} -Kevin -- ------------------------------------------------------------------------ | Kevin O'Connor "BTW, IMHO we need a FAQ for | | kevin@koconnor.net 'IMHO', 'FAQ', 'BTW', etc. !" | ------------------------------------------------------------------------

There's just no contest here. BTrees have many other virtues, like supporting range searches, and automatically playing nice with ZODB persistence, but they're plain sluggish compared to dicts. To be completely fair and unfair at the same time <wink>, there are also 4 other flavors of Zope BTree, purely for optimization reasons. In particular, the IIBTree maps Python ints to Python ints, and does so by avoiding Python int objects altogether, storing C longs directly and comparing them at native "compare a long to a long" C speed. That's *almost* as fast as Python 2.1 int->int dicts (which endure all-purpose Python object comparison), except for deletion (the BTree spends a lot of time tearing apart all the tree

again).

Now that's a perfectly height-balanced search tree that "chunks up" blocks of keys for storage and speed efficiency, and rarely needs more than a simple local adjustment to maintain balance. I expect that puts it at

This is really interesting. When I was at Dragon (well, actually, after Tim left and it became L&H), I ported my natural language parsing/understanding system from Python to C++ so it could run quickly enough for embedded devices. The core of this system was an associative container, so I knew that its performance would be crucial. I used C++ generics which made it really easy to swap in different associative container implementations, and I tried lots, including the red-black tree containers built into most C++ implementations, and hash tables. My experience was that trying to come up with a hash function that would give a significant speed increases over the tree containers was extremely difficult, because it was really hard to come up with a good hash function. Furthermore, even if I succeeded, it was like black magic: it was inconsistent accross my test cases and there was no way to understand why it worked well, and to get a feeling for how it would scale to problems outside those cases. I ended up hand-coding a two-level scheme based on binary searches in contiguous arrays which blew away anything I'd been able to do with a hash table. My conclusion was that for general-purpose use, the red-black tree was pretty good, despite its relatively high memory overhead of 3 pointers per node: it places easy requirements on the user (supply a strick weak ordering) and provides predictable and smooth performance even asymptotically. On the other hand, hashing requires that the user supply both a hash function and an equality detector which must agree with one-another, requires hand-tuning of the hash function for performance, and is rather more unpredictable. We've been talking about adding hash-based containers to the C++ standard library but I'm reluctant on these grounds. It seems to me that when you really care about speed, some kind of hand-coded solution might be a better investment than trying to come up with a good hash function. I'm ready to believe that hashing is the most appropriate choice for Python, but I wonder what makes the difference? -Dave From: "Tim Peters" pointers the

fast end of what can be achieved with a balanced tree scheme.

The ABC language (which Guido worked on before Python) used AVL trees for just about everything under the covers. It's not a coincidence that Python doesn't use balanced trees for anything <wink>.

_______________________________________________ Python-Dev mailing list Python-Dev@python.org http://mail.python.org/mailman/listinfo/python-dev

From: "Tim Peters"

There's more to a speedy hash implementation than just the hash function, of course.

'course.

...

Furthermore, even if I succeeded, it was like black magic: it was < inconsistent accross my test cases and there was no way to understand why it worked well, and to get a feeling for how it would scale to problems outside those cases.

Python's dictobject.c and .h have extensive comments about how Python's dicts work. Their behavior isn't mysterious, at least not after 10 years of thinking about it <0.9 wink>. Python's dicts also use tricks that I've never seen in print -- many people have contributed clever tricks.

I noticed that, and I think the next time I try hashing I'm going to steal as much as possible from Python's implementation to get a head start. Noticing that also left me with a question: how come everybody in the world hasn't stolen as much as possible from the Python hashing implementation? Are there a billion such 10-years'-tweaked implementations lying around which all perform comparably well?

The example I posted built a mapping with a million entries. A red-black tree of that size needs to chase between 20 and 40 pointers to determine membership. By sheer instruction count alone, that's way more instructions than the Python dict usually has to do, although it's comparable to the number the BTree had to do. The BTree probably has better cache behavior than a red-black tree; for example, all the keys in the million-element example were on the third level, and a query required exactly two pointer-chases to get to the right leaf bucket. All the rest is binary search on 60-120 element contiguous vectors (in fact, sounds a lot like your custom "two-level scheme")

Yeah, I think it ended up being something like that. Of course, the container I ended up with used domain-specific knowledge which would have been inappropriate for general-purpose use.

...

it places easy requirements on the user (supply a strick weak ordering) and provides predictable and smooth performance even asymptotically.

OTOH, it can be very hard to write an efficient, correct "<" ordering, while testing just "equal or not?" can be easier and run quicker than that. Dict comparison is a good example from the Python core: computing "<" for dicts is a nightmare, but computing "==" for dicts is easy (contrast the straightforward dict_equal() with the brain-busting dict_compare() + characterize() pair).

Well, OK, ordering hash tables is hard, unless the bucket count is a deterministic function of the element count. If they were sorted containers, of course, < would be a simple matter. And I assume that testing equality still involves a lot of hashing... Hmm, looking at the 3 C++ implementations of hashed containers that I have available to me, only one provides operator<(), which is rather strange since the other two implement operator== by first comparing sizes, then iterating through consecutive elements of each set looking for a difference. The implementation supplying operator<() uses a (IMO misguided) design that rehashes incrementally, but it seems to me that if the more straightforward approaches can implement operator==() as described, operator<() shouldn't have to be a big challenge for an everyday hash table. I'm obviously missing something, but what...?

This was one of the motivations for introducing "rich comparisons".

I don't see how that helps. Got a link? Or a clue?

...

On the other hand, hashing requires that the user supply both a hash function and an equality detector which must agree with one-another,

I've rarely found this to be a challenge. For example, for sets that contain sets as elements, a suitable hash function can simply xor the hash codes of the set elements. Since equal sets have equal elements, such a scheme delivers equal hash codes for equal sets, and independent of the order in which set elements get enumerated. In contrast, defining a sensible *total* ordering on sets is a delicate undertaking (yes, I know that "strict weak ordering" is weaker than "total", but in real life you couldn't buy a hot dog with the difference <wink>).

I don't know what that means. If you represent your sets as sorted containers, getting a strict weak ordering on sets is trivial; you just do it with a lexicographical comparison of the two sequences.

...

I'm ready to believe that hashing is the most appropriate choice for Python, but I wonder what makes the difference?

Well, I'm intimately familar with the details of how Python dicts and Zope BTrees are implemented, down to staring at the machine instructions generated, and there's no mystery here to me. I'm not familiar with any of the details of what you tried. Understanding speed differences at this level isn't a "general principles" kind of discussion.

I should note that Zope's BTrees pay a lot for playing nice with persistence, about a factor of two: upon visiting and leaving each BTree node, there are messy test+branch sequences ensuring that the object isn't a ghost, notifying the persistence machinery that fields have been accessed and/or changed, and telling the persistence machinery when the object is no longer in active use. Most of these bookkeeping operations can fail too, so there's another layer of "and did that fail?" test+branches around all

The saving grace for BTrees (why this doesn't cost a factor of, say, 10) is that each BTree node contains a fair amount of "stuff", so that the guts of each function can do a reasonable amount of useful work. The persistence overhead could be a disaster if visiting an object only moved one bit closer to the result.

But Python's dicts aren't aware of persistence at all, and that did give dicts an ~= factor-of-2 advantage in the example. While they're still not as zippy as dicts after factoring that out, B-Trees certainly aren't

No, I suppose not. But python's dicts are general-purpose containers, and you can put any key you like in there. It's still surprising to me given my (much less than 10 years') experience with hash implementations that you can design something that performs well over all those different cases. that. Aww, heck, you just need a good C++ exception-handling implementation to get rid of the error-checking overheads ;-) pigs.

BTW, note that Python's dicts originally catered only to string keys, as they were the implementation of Python's namespaces, and dicts remain

optimized for that specific purpose. Indeed, there's a distinct dict lookup routine dedicated to dicts with string keys. Namespaces have no compelling use for range search or lexicographic traversal, just association, and

highly peak

lookup speed was the design imperative.

Thanks for the perspective! still-learning-ly y'rs, dave

[David Abrahams]

Noticing that also left me with a question: how come everybody in the world hasn't stolen as much as possible from the Python hashing implementation? Are there a billion such 10-years'-tweaked implementations lying around which all perform comparably well?

[Gordon McMillan]

Jean-Claude Wippler and Christian Tismer did some benchmarks against other implementations. IIRC, the only one in the same ballpark was Lua's (which, IIRC, was faster at least under some conditions).

I'd like to see the benchmark. Like Python, Lua uses a power-of-2 table size, but unlike Python uses linked lists for collisions instead of open addressing. This appears to leave it very vulnerable to bad cases (like using [i << 16 for i in range(20000)] as a set of keys -- Python and Lua both grab the last 15 bits of the ints as their hash codes, which means every key maps to the same hash bucket. Looks like Lua would chain them all together. Python breaks the ties quickly via its collision resolution scrambling.). The Lua string hash appears systematically vulnerable: static unsigned long hash_s (const char *s, size_t l) { unsigned long h = l; /* seed */ size_t step = (l>>5)|1; /* if string is too long, don't hash all its chars */ for (; l>=step; l-=step) h = h ^ ((h<<5)+(h>>2)+(unsigned char)*(s++)); return h; } That hash function would be weak even if it didn't ignore up to 97% of the input characters. OTOH, if it happens not to collide, ignoring up to 97% of the characters eliminates up to 97% of the expense of computing a hash. Etc. Lua's hashes do appear to get a major benefit from lacking a Python feature: user-defined comparisons can (a) raise exceptions, and (b) mutate the hash table *while* you're looking for a key in it. Those cause the Python implementation lots of expensive pain (indeed, the main reason Python has a distinct lookup function for string-keyed dicts is that it doesn't have to choke itself worrying about #a or #b for builtin strings). There's a lovely irony here. Python's dicts are fast because they've been optimized to death. When Lua's dicts are fast, it seems more the case it's because they don't worry much about bad cases. That's *supposed* to be Python's trick <wink>.

[David Abrahams]

...

... Noticing that also left me with a question: how come everybody in the world hasn't stolen as much as possible from the Python hashing implementation? Are there a billion such 10-years'-tweaked implementations lying around which all perform comparably well?

It's a Mystery, and in all directions. Python has virtually no code from, say, Tcl or Perl either, and the latter certainly do some things better

----- Original Message ----- From: "Tim Peters" To: "David Abrahams" Cc: Sent: Friday, June 28, 2002 1:01 AM Subject: RE: [Python-Dev] Priority queue (binary heap) python code than

Python does them. I've studied all their hash implementations, but didn't find anything worth stealing <wink>;

Well of course not!

OTOH, multiple attempts by multiple groups to steal Perl's regexp engine years ago fizzled out in a tarpit of frustration.

Oh, I had the impression that Python's re *was* pilfered Perl.

Curious: Python independently developed a string hash *very* similar to what later became "the standard" Fowler-Noll-Vo string hash:

http://www.isthe.com/chongo/tech/comp/fnv/

The multiplier is different, and the initial value, but that's it. I'm sure there was no communication in either direction. So ya, given enough time, a billion other projects will rediscover it too.

Nifty.

...

Well, OK, ordering hash tables is hard, unless the bucket count is a deterministic function of the element count.

I don't know how the latter could help; for that matter, I'm not even sure what it means.

I know what I meant, but I was wrong. My brain cell musta jammed. Ordering hash tables is hard if collisions are possible.

...

And I assume that testing equality still involves a lot of hashing...

No more times than the common length of the two dicts.

Of course.

It's just:

def dict_equal(dict1, dict2): if len(dict1) != len(dict2): return False for key, value in dict1.iteritems(): if key not in dict2 or not value == dict2[key]: return False return True

Searching dict2 for key *may* involve hashing key again (or it may not; for example, Python string objects are immutable and cache their 32-bit hash in the string object the first time it's computed).

Tricky. I guess a C++ object could be designed to cooperate with hash tables in that way also.

There's a world of pain involved in the "==" there, though, as a dict can very well have itself as a value in itself, and the time required for completion appears to be exponential in some pathological cases of that kind (Python does detect the unbounded recursion in such cases -- eventually).

...

Hmm, looking at the 3 C++ implementations of hashed containers that I have available to me, only one provides operator<(), which is rather strange since the other two implement operator == by first comparing sizes,

Yuck. I wouldn't expect any C++ implementation to handle that issue. then

...

iterating through consecutive elements of each set looking for a difference. The implementation supplying operator<() uses a (IMO misguided) design that rehashes incrementally, but it seems to me that if the more straightforward approaches can implement operator==() as described, operator<() shouldn't have to be a big challenge for an everyday hash table.

I'm obviously missing something, but what...?

I don't know, but I didn't follow what you were saying (like, "rehashes incrementally" doesn't mean anything to me).

If there's a simpler way to get "the right" answer, I'd love to see it. I once spent two hours

Get ahold of MSVC7 and look at the hash_set implementation. IIRC how Plaugher described it, it is constantly maintaining the load factor across insertions, so there's never a big cost to grow the table. It also keeps the items in each bucket sorted, so hash table comparisons are a lot easier. My gut tells me that this isn't worth what you pay for it, but so far my gut hasn't had very much of any value to say about hashing... The other implementations seem to implement equality as something like: template inline bool operator==(const hash_set& x, const hash_set& y) { return x.size() == y.size() && std::equal(x.begin(), x.end(), y.begin()); } Which has to be a bug unless they've got a very strange way of defining equality, or some kindof ordering built into the iterators. trying

to prove that the dict_compare() + characterize() pair in Python was correct, but gave up in a mushrooming forest of end cases.

I think it's a tougher problem in Python than in languages with value semantics, where an object can't actually contain itself.

In The Beginning, Python implemented dict comparison by materializing the .items(), sorting both, and then doing list comparison. The correctness of that was easy to show. But it turned out that in real life all anyone ever used was == comparison on dicts, and sorting was enormously expensive compared to what was possible. characterize() is a very clever hack Guido dreamt up to get the same result in no more than two passes -- but I've never been sure it's a thoroughly correct hack.

??? I can't find characterize() described anywhere, nor can I find it on my trusty dict objects:

...

...

help({}.characterize) Traceback (most recent call last): File "<stdin>", line 1, in ? AttributeError: 'dict' object has no attribute 'characterize'

OTOH, since nobody appears to care about "<" for dicts, if it's wrong we may never know that.

As long as the Python associative world is built around hash + ==, you're probably OK.

...

...

This was one of the motivations for introducing "rich comparisons".

...

I don't see how that helps. Got a link? Or a clue?

Sorry, I don't understand the question.

Well, you answered it pretty damn well anyway...

Comparing strings for equality/inequality alone is also done faster than needing to resolve string ordering. And complex numbers have no accepted "<" relation at all.

So comparing dicts isn't the only place it's easier and quicker to restrict the burden on

Yeah, good point. C++ has a less<T>/operator< dichotomy mostly to accomodate pointer types in segmented memory models, but there's no such accomodation for complex<T>. the

type to implementing equality testing. For user-defined types, I've often found it *much* easier. For example, I can easily tell whether two chessboards are equal (do they have the same pieces on the same squares?), but a concept of "<" for chessboards is strained.

Strained, maybe, but easy. You can do a lexicographic comparison of the square contents.

...

I don't know what that means.

There's too much of that on both sides here, so I delcare this mercifully ended now <0.9 wink>.

I, of course, will drag it on to the bitter end.

[on Zope's B-Trees]

...

Aww, heck, you just need a good C++ exception-handling implementation

to

...

get rid of the error-checking overheads ;-)

I'd love to use C++ for this. This is one of those things that defines 5 families of 4 related data structures each via a pile of .c and .h files that get #include'd and recompiled 5 times after #define'ing a pile of macros. It would be *so* much more pleasant using templates.

I have *just* the library for you. Works with 'C', too! http://www.boost.org/libs/preprocessor/doc/ Believe it or not, people are still pushing this technology to improve compilation times and debuggability of the result.

...

... Thanks for the perspective!

still-learning-ly y'rs,

You're too old for that now -- start making money instead <wink>.

Sorry, I'll try hard to grow up now. -Dave

From: "Aahz"

...

Oh, I had the impression that Python's re *was* pilfered Perl.

Thank Fredrik for a brilliant job of re-implementing Perl's regex syntax into something that I assume is maintainable (haven't looked at the code myself) *and* Unicode compliant.

Thanks, Fredrik!

david wrote:

...

OTOH, multiple attempts by multiple groups to steal Perl's regexp engine years ago fizzled out in a tarpit of frustration.

Oh, I had the impression that Python's re *was* pilfered Perl.

Tim warned me that the mere attempt to read sources for existing RE implementations was a sure way to destroy my brain, so I avoided that. SRE is a clean-room implementation, using the Python 1.5.2 docs and the regression test suite as the only reference. I've never written a Perl regexp in my life. </F>

[Oren Tirosh]

A sorted list is a much more general-purpose data structure than a priority queue and can be used to implement a priority queue. [...] The only advantage of a heap is O(1) peek which doesn't seem so critical. [...] the internal order of a heap-based priority queue is very non-intuitive and quite useless for other purposes while a sorted list is, umm..., sorted!

It surely occurred to many of us to sort a file (or any set of data) from the most interesting entry to the least interesting entry, look at the first 5% to 10%, and drop all the rest. A heap is a good way to retain the first few percents of items, without going through the lengths of fully sorting all the rest. By comparison, it would not be efficient to use `.sort()' then truncate. Within a simulation, future events are scheduled while current events are being processed, so we do not have all the events to `.sort()' first. It is likely that heaps would beat insertion after binary search, given of course that both are implemented with the same care, speed-wise. -- François Pinard http://www.iro.umontreal.ca/~pinard

[Guido van Rossum]

Oh, and maybe we can borrow a few lines of François's description of the algorithm. :-)

Borrow liberally! I would prefer that nothing worth remains un-borrowed from mine, so I can happily get rid of my copy when the time comes! :-)

I propose to call it heapq.py. (Got a better name? Now or never.)

I like `heapq' as it is not an English common name, like `heap' would be, so less likely to clash with user chosen variable names! This principle should be good in general. Sub-classing `heapq' from `list' is a good idea! P.S. - In other languages, I have been using `string' a lot, and this has been one of the minor irritations when I came to Python, that it forced me away of that identifier; so I'm now using `text' everywhere, instead. Another example is the name `socket', which is kind of reserved from the module name, I never really know how to name variables holding sockets :-). -- François Pinard http://www.iro.umontreal.ca/~pinard

[Guido van Rossum]

[...] I admire the compactness of his code. I believe that this would make a good addition to the standard library, as a friend of the bisect module. [...] The only change I would make would be to make heap[0] the lowest value rather than the highest. I propose to call it heapq.py.

[Kevin O'Connor]

Looks good to me.

In case you going forward with `heapq', and glancing through my notes, I see that "Courageous" implemented a priority queue algorithm as a C extension, and discussed it on python-list on 2000-05-29. I'm not really expecting that you aim something else than a pure Python version, and I'm not pushing nor pulling for it, as I do not have an opinion. In any case, I'll keep these messages a few more days: just ask, and I'll send you a copy of what I saved at the time. P.S. - I'm quickly loosing interests in these bits of C code meant for speed, as if I ever need C speed, the wonderful Pyrex tool (from Greg Ewing) gives it to me while allowing the algorithm to be expressed in a language close to Python. I even wonder if Pyrex could not be a proper avenue for the development of some parts of the Python distribution itself. -- François Pinard http://www.iro.umontreal.ca/~pinard

[Magnus Lie Hetland]

I see that heapq is now in the libraries -- great!

Just one thought: If I want to use this library in an algorithm such as, say, Dijkstra's single-source shortest path algorithms, I would need an additional operation, the deacrease-key operation

You'd need more than just that <wink>.

(as far as I can see, the heapreplace only works with index 0 -- wy is that?)

heapreplace() is emphatically not a decrease-key operation. It's equivalent to a pop-min *followed by* a push, which combination is often called a "hold" operation. The value added may very well be larger than the value popped, and, e.g., the example of an efficient N-Best queue in the test file relies on this. Hold is an extremely common operation in some kinds of event simulations too, where it's also most common to push a value larger than the one popped (e.g., when the queue is ordered by scheduled time, and the item pushed is a follow-up event to the one getting popped).

E.g.:

def heapdecrease(heap, index, item): """ Replace an item at a given index with a smaller one.

May be used to implement the standard priority queue method heap-decrease-key, useful, for instance, in several graph algorithms. """ assert item <= heap[index]

That's the opposite of what heapreplace() usually sees.

heap[index] = item _siftdown(heap, 0, index)

Something might perhaps be useful to include in the library...

I really don't see how -- you generally have no way to know the correct index short of O(N) search. This representation of priority queue is well-known to be sub-optimal for applications requiring frequent decrease-key (Fibonacci heaps were desgined for it, though, and pairing heaps are reported to run faster than Fibonacci heaps in practice despite that one of the PH inventors eventually proved that decrease-key can destroy PH's otherwise good worst-case behavior).

Or, perhaps, the _siftup and _siftdown methods don't have to be private?

You really have to know what you're doing to use them correctly, and it's dubious that _siftup calls _siftdown now (it's most convenient *given* all the uses made of them right now, but, e.g., if a "delete at arbitrary index" function were to be added, _siftdown and _siftup could stand to be refactored -- exposing them would inhibit future improvements).

In addition, I guess one would have to implement a sequence class that maintained a map from values to heap indices to be able to use heapdecrease in any useful way (otherwise, how would you know which index to use?).

Bingo. All the internal heap manipulations would have to know about this mapping too, in order to keep the indices up to date as it moved items up and down in the queue. If want you want is frequent decrease-key, you don't want this implementation of priority queues at all.