On 5/1/03 2:13 AM -0400 Tim Peters <tim_one@email.msn.com> wrote: > It surprised me that you tried using heapq at all for this algorithm. I > was also surprised that you succeeded <0.9 wink>. Wink noted, but it surprised me too, a little. I had thought decrease key was a necessary part of the algorithm, not something that could be finessed like that. > You can wrap any interface you like around heapq (that's very easy to do > in Python), but it won't change that heapq's implementation is poorly > suited to this application. priorityDictionary looks like an especially > nice API for this specific algorithm, but, e.g., impossible to use > directly for maintaining an N-best queue (priorityDictionary doesn't > support multiple values with the same priority, right? if we're trying > to find the 10,000 poorest people in America, counting only one as dead > broke would be too Republican for some peoples' tastes <wink>). OTOH, > heapq is easy and efficient for *that* class of heap application. I agree with your main points (heapq's inability to handle certain priority queue applications doesn't mean it's useless, and its implementation-specific API helps avoid fooling programmers into thinking it's any more than what it is). But I am confused at this example. Surely it's just as easy to store (income,identity) tuples in either data structure. If you mean, you want to find the 10k smallest income values (rather than the people having those incomes), then it may be that a better data structure would be a simple list L in which the value of L[i] is the count of people with income i. -- David Eppstein http://www.ics.uci.edu/~eppstein/ Univ. of California, Irvine, School of Information & Computer Science
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4