[Python-ideas] Optional key to `bisect`'s functions?
stutzbach at google.com
Thu Feb 9 18:50:19 CET 2012
On Wed, Feb 8, 2012 at 4:25 PM, Guido van Rossum <guido at python.org> wrote:
> Also note that "many times" is actually O(log N) per insertion, which
> isn't so bad. The main use case for bisect() is to manage a list that sees
> updates *and* iterations -- otherwise building the list unsorted and
> sorting it at the end would make more sense. The key= option provides a
> balance between the cost/elegance for updates and for iterations.
Maintaining a sorted list using Python's list type is a trap. The bisect
is O(log n), but insertion and deletion are still O(n).
A SortedList class that provides O(log n) insertions is useful from time to
time. There are several existing implementations available (I wrote one of
them, on top of my blist type), each with their pros and cons.
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Python-ideas