[Python-ideas] Optional key to `bisect`'s functions?

Raymond Hettinger raymond.hettinger at gmail.com
Thu Feb 9 21:16:45 CET 2012


On Feb 9, 2012, at 9:50 AM, Daniel Stutzbach wrote:

> 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.

I concur.  People who want to maintain sorted collections (periodically adding and deleting items) are far better-off using your blist, a binary tree, or an in-memory sqlite database.  Otherwise, we will have baited them into a non-scalable O(n) solution.  Unfortunately, when people see the word "bisect", they will presume they've got O(log n) code.  We've documented the issue with bisect.insort(), but the power of suggestion is very strong.


Raymond 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-ideas/attachments/20120209/9095f669/attachment.html>


More information about the Python-ideas mailing list