<div dir="ltr">This thread is not about hash tables.  This thread is about indexing into an ordered dictionary when you need an ordered dictionary.  Someone pointed out that people expect indexing to be constant time.  I agree that no one expects indexing to be linear time.  My point was that logarithmic-time indexing is reasonable and possible.</div><div class="gmail_extra"><br><div class="gmail_quote">On Tue, Jul 7, 2015 at 12:15 AM, Andrew Barnert <span dir="ltr"><<a href="mailto:abarnert@yahoo.com" target="_blank">abarnert@yahoo.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="auto"><span class=""><div>On Jul 6, 2015, at 15:04, Neil Girdhar <<a href="mailto:mistersheik@gmail.com" target="_blank">mistersheik@gmail.com</a>> wrote:</div><div><br></div><blockquote type="cite"><div><div dir="ltr">You can do indexing, insertion, and removal all in logarithmic time (which is basically constant) </div></div></blockquote><div><br></div></span><div>If you're dealing with dicts of, say, millions of items, then it's "basically constant" with a multiplier of 6-20x worse than the current implementation, and only as long as you never need to scale larger (which is a pretty major concern if you're writing a general-purpose library or something). That's not the same thing as actually constant. There's a reason all the scripting languages have hash-based containers, and that the systems languages that started off with only tree-based containers later added hash-based containers as well.</div><div><br></div><div>Personally, I think it would be great if Python had tree-based sorted containers alongside the existing hash-based arbitrary-ordered ones. Then it would be trivial to add a tree-based insertion-order container to replace the hash-based insertion-order container when it's more appropriate to a specific use (e.g., when you need to efficiently random-access-index it). But, unless you're doing government work or something else that has no access to PyPI, that's already true today, so there's not much to wish for.</div><div><div class="h5"><br><blockquote type="cite"><div><div dir="ltr">by using a B-tree as the underlying data structure.  (See e.g. the blist package.)</div><div class="gmail_extra"><br><div class="gmail_quote">On Mon, Jul 6, 2015 at 5:59 PM, Eric Snow <span dir="ltr"><<a href="mailto:ericsnowcurrently@gmail.com" target="_blank">ericsnowcurrently@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span>On Mon, Jul 6, 2015 at 3:30 PM, Neil Girdhar <<a href="mailto:mistersheik@gmail.com" target="_blank">mistersheik@gmail.com</a>> wrote:<br>
</span><span>> SortedDict (<a href="http://www.grantjenks.com/docs/sortedcontainers/sorteddict.html" rel="noreferrer" target="_blank">http://www.grantjenks.com/docs/sortedcontainers/sorteddict.html</a>)<br>
> manages to support indexing.  Can OrderedDict do the same thing?<br>
<br>
</span>Don't forget that, as the docs describe, an "OrderedDict is a dict<br>
that remembers the order that keys were first inserted".  While<br>
obviously there's an implicit sequence for that order, the focus is<br>
still on dict-ness with the sequence exposed through the normal<br>
mapping approach (iteration).  If you want to get sequence semantics<br>
then first unpack the order into a sequence type like list or tuple.<br>
Or use some other type than OrderedDict.<br>
<br>
Note that OrderedDict's view types are essentially just dict's view<br>
types with custom iteration.  Adding indexing to the views would<br>
complicate things and certainly would not be O(1) like you would<br>
expect indexing to be.<br>
<span><font color="#888888"><br>
-eric<br>
</font></span></blockquote></div><br></div>
</div></blockquote></div></div><blockquote type="cite"><div><span class=""><span>_______________________________________________</span><br><span>Python-ideas mailing list</span><br><span><a href="mailto:Python-ideas@python.org" target="_blank">Python-ideas@python.org</a></span><br></span><span class=""><span><a href="https://mail.python.org/mailman/listinfo/python-ideas" target="_blank">https://mail.python.org/mailman/listinfo/python-ideas</a></span><br><span>Code of Conduct: <a href="http://python.org/psf/codeofconduct/" target="_blank">http://python.org/psf/codeofconduct/</a></span></span></div></blockquote></div></blockquote></div><br></div>