<html><head></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><br><div><div>On Feb 9, 2012, at 9:50 AM, Daniel Stutzbach wrote:</div><br class="Apple-interchange-newline"><blockquote type="cite"><span class="Apple-style-span" style="border-collapse: separate; font-family: Helvetica; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; -webkit-text-decorations-in-effect: none; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; font-size: medium; "><div>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).</div><div><br></div><div>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.</div></span></blockquote></div><br><div>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.</div><div><br></div><div><br></div><div>Raymond </div></body></html>