<html><head><meta http-equiv="Content-Type" content="text/html charset=us-ascii"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;"><br><div><div>On Mar 26, 2014, at 1:31 PM, Marko Rauhamaa <<a href="mailto:marko@pacujo.net">marko@pacujo.net</a>> wrote:</div><br class="Apple-interchange-newline"><blockquote type="cite"><span style="font-family: ArialMT; font-size: 16px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; float: none; display: inline !important;">I have made a full implementation of a balanced tree and would like to</span><br style="font-family: ArialMT; font-size: 16px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;"><span style="font-family: ArialMT; font-size: 16px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; float: none; display: inline !important;">know what the process is to have it considered for inclusion in Python</span><br style="font-family: ArialMT; font-size: 16px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;"><span style="font-family: ArialMT; font-size: 16px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; float: none; display: inline !important;">3.</span><br style="font-family: ArialMT; font-size: 16px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;"><br style="font-family: ArialMT; font-size: 16px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;"><span style="font-family: ArialMT; font-size: 16px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; float: none; display: inline !important;">To summarize, the implementation closely parallels dict() features and</span><br style="font-family: ArialMT; font-size: 16px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;"><span style="font-family: ArialMT; font-size: 16px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; float: none; display: inline !important;">resides in _collectionsmodule.c under the name collections.sortedtree.</span><br style="font-family: ArialMT; font-size: 16px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;"><span style="font-family: ArialMT; font-size: 16px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; float: none; display: inline !important;">It uses solely the "<" operator to compare keys. I have chosen the AVL</span><br style="font-family: ArialMT; font-size: 16px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;"><span style="font-family: ArialMT; font-size: 16px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; float: none; display: inline !important;">tree as an implementation technique.</span></blockquote></div><div><br></div><div>FWIW, I think there may be room for a sorted collection somewhere in the</div><div>standard library.</div><div><br></div><div>As others have said, the best place to start is by putting a module on PyPi</div><div>to let it mature and to compete with other approaches to the problem.</div><div><br></div><div>Here are a few random thoughts on the over-all idea:</div><div><br></div><div>* An AVL balanced tree isn't the only solution or necessarily the best solution</div><div>to the problem. Tree nodes tend to take more space than denser</div><div>structures and they have awful cache locality (these are the same reasons</div><div>that deques use doubly-linked blocks rather than a plain doubly linked lists).</div><div><br></div><div>* Another approach I have experimented with uses lazy sorting. That lets</div><div>insertion be an O(1) step and incurs a one-time sorting cost upon the next</div><div>lookup (and because Timsort exploits partial orderings, this can be very</div><div>cheap). A lazy sorted list is dense and sequentially ordered in memory</div><div>(reducing space overhead, taking full advantage of cache locality and memory</div><div>controller auto-prefetch, and providing fast iteration speed by not needing</div><div>to chase pointers). The lazy sort approach works best in applications that</div><div>spend most of the time doing lookups and have only infrequent deletions</div><div>and insertions.</div><div><br></div><div>* The name of the tool probably should not be sortedtree. Ideally, the tool</div><div>should be named for what it does, not how it does it (for the most part,</div><div>users don't need to know whether the underlying implementation is</div><div>a red-black tree, b-tree, judy array, sqlite database, or lazy list). That</div><div>is why (I think) that Python dicts are called dicts rather than hash tables</div><div>(the implementation) or an associative array (the computer science term</div><div>for the abstract datatype).</div><div><br></div><div>* There are plenty of data structures that have had good utility and</div><div>popularity outside of the standard library. I that it is a good thing that</div><div>blists, numpy arrays, databases, and panda dataframes all live outside</div><div>the standard library. Those tools are easier to maintain externally and</div><div>it is easier for you to keep control over the design. Remember the saying,</div><div>"the standard library is where code goes to die" (and I would add that it</div><div>should already be mature (or nearly dead) by the time it gets there). </div><div><br></div><div>* That said, it is a reasonable possibility that the standard library would</div><div>benefit from some kind sorted collection (the idea comes up from time</div><div>to time).</div><div><br></div><div> </div><div> Raymond Hettinger</div></body></html>