Issue1162363
This issue tracker has been migrated to GitHub,
and is currently read-only.
For more information,
see the GitHub FAQs in the Python's Developer Guide.
Created on 2005-03-13 10:45 by scoder, last changed 2022-04-11 14:56 by admin. This issue is now closed.
Files | ||||
---|---|---|---|---|
File name | Uploaded | Description | Edit | |
heapq.py.diff | scoder, 2005-03-14 13:14 | Version fixing cmp/key interaction |
Messages (7) | |||
---|---|---|---|
msg47954 - (view) | Author: Stefan Behnel (scoder) * | Date: 2005-03-13 10:45 | |
Bug 1158313 (requesting functions for heap iteration) was rejected, one of the reasons being that iteration does not fit well with the module design providing helper functions. Here is an implementation of a Heap class for that module that encapsulates a list. It supports iteration as well as the usual keyword arguments passed to sort() or sorted(): key, cmp, reversed. It further supports skipping the heapify step (heapify=True/False) when constructing the heap as well as copying the list if unnecessary (copy=True/False). The latter is generally discouraged and not the default. It is, however, useful for one-shot sequence generation as in >>> h = Heap([ random() for i in range(1000) ], copy=False) A further feature (somewhat obvious for heaps) is that iteration is not interrupted by items being pushed on the heap, they are simply integrated. "heapreplace" is supported by a "pushpop" function as initially proposed by R. Hettinger. It always returns the smallest item, also considering the one being pushed. This implementation is complementary to the existing functions that work on arbitrary (mutable) sequences. Both have their use cases and both make sense in the module. The Heap class has the additional advantage of encapsulating the list and thus allowing to support special item comparisons in a consistent way. There is not yet any documentation or unit tests, but they should be easy to write once the Heap class is actually considered for integration. |
|||
msg47955 - (view) | Author: Stefan Behnel (scoder) * | Date: 2005-03-13 11:00 | |
Logged In: YES user_id=313935 Forgot undecoration in __getitem__ method. Updated patch. |
|||
msg47956 - (view) | Author: Stefan Behnel (scoder) * | Date: 2005-03-14 12:15 | |
Logged In: YES user_id=313935 The semantics of combining cmp and key are not specified in the Python documentation and my last implementation differed from the semantics of sort() and sorted() in that regard. The new patch fixes this and does some clean up. It also introduces a method iter_clone() that returns an independent iterator. |
|||
msg47957 - (view) | Author: Stefan Behnel (scoder) * | Date: 2005-03-14 12:18 | |
Logged In: YES user_id=313935 assigned to rhettinger |
|||
msg47958 - (view) | Author: Stefan Behnel (scoder) * | Date: 2005-03-14 13:14 | |
Logged In: YES user_id=313935 The things that pychecker doesn't tell you ... |
|||
msg47959 - (view) | Author: Martin v. Löwis (loewis) * | Date: 2007-03-06 13:38 | |
Can you please provide patches to Doc/lib/libheapq.tex and Lib/test/test_heapq.py? Please also put doc strings into the class. Please drop the type assertions in __init__. I find it quite magical that it will silently turn copy on if the iterator doesn't support len or indexing. Why is iteration through the heap destructive? No other container has that feature. Putting the sanity checks into the module isn't necessary - just use the regular test suite for that. I can't comment further - lack of comments in the patch prevents me from actually understanding it. In the current form, I recommend rejection. Unassigning Raymond. |
|||
msg64396 - (view) | Author: Raymond Hettinger (rhettinger) * | Date: 2008-03-24 08:04 | |
Overall, I'm not in favor of the patch or the basic idea. The heapq module is somewhat usable as-is with apps typically inserting tuples linking a priority level and a record. Also, the attached code is not yet mature, nor does it evidence compelling use cases or user demand. This may make a good ASPN recipe but would be premature for inclusion in the standard library. One quick comment on the API, it would be better to have just a key function and to drop the cmp function as Python itself has done throughout the language in Py3.0. Recommend rejecting the feature request, leaving the module as clean as possible. If the code is published separately (perhaps as an ASPN recipe or third-party module), it may yet mature and gather a fan club. |
History | |||
---|---|---|---|
Date | User | Action | Args |
2022-04-11 14:56:10 | admin | set | github: 41689 |
2008-03-24 08:04:33 | rhettinger | set | status: open -> closed resolution: rejected messages: + msg64396 |
2005-03-13 10:45:15 | scoder | create |