[Matthias Urlichs] > Oren Tirosh <oren-py-d@hishome.net>: > > When I want to sort a list I just use .sort(). I don't care which > > algorithm is used. > The point in this discussion, though, is that frequently you don't need > a sorted list. You just need a list which yields all elements in order > when you pop them. Heaps are a nice low-overhead implementation of that > idea, and therefore should be in the standard library. This is especially true when you need only the first few elements from the sorted set, which is a pretty common case in practice. A blind sort is not always the optimal solution, when you want to spare some CPU time. A caricatural example of abuse would be to implement `max' as `sort' followed by peeking at the first element of the result. Heaps are also an efficient enough representation if you insert while sorting, as it often happens in simulations. Someone I know studied this intensely, and came up with better algorithms on average of his reference benchmark, but with much worse worst cases -- so it depends of the characteristics of the simulation. Heaps do quite well on average, and do acceptably well also in their worst cases. -- François Pinard http://www.iro.umontreal.ca/~pinard
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