<div dir="ltr">Yeah, but logarithmic time everything should be good enough for nearly all problems.  After years of programming competitions, one thing I remember is how hard it is to craft a problem such that a linear solution is accepted, but a linearithmic one is not.</div><div class="gmail_extra"><br><div class="gmail_quote">On Tue, Jul 7, 2015 at 4:33 AM, Masklinn <span dir="ltr"><<a href="mailto:masklinn@masklinn.net" target="_blank">masklinn@masklinn.net</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span class="">On 2015-07-07, at 06:23 , Neil Girdhar <<a href="mailto:mistersheik@gmail.com">mistersheik@gmail.com</a>> wrote:<br>
<br>
> 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.<br>
<br>
</span>Linear time indexing would be possible by changing the OrderedDict implementation to Raymond Hettinger's compact dictionaries[0] with a delete operation recompacting the entries array rather than just nulling the item (it would make removals on "early" keys of large dictionaries more expensive though, delete would become O(n) with n the number of "living" entries added after the one being removed).<br>
<br>
[0] <a href="https://mail.python.org/pipermail/python-dev/2012-December/123028.html" rel="noreferrer" target="_blank">https://mail.python.org/pipermail/python-dev/2012-December/123028.html</a><br>
<span class="im HOEnZb">_______________________________________________<br>
Python-ideas mailing list<br>
<a href="mailto:Python-ideas@python.org">Python-ideas@python.org</a><br>
<a href="https://mail.python.org/mailman/listinfo/python-ideas" rel="noreferrer" target="_blank">https://mail.python.org/mailman/listinfo/python-ideas</a><br>
Code of Conduct: <a href="http://python.org/psf/codeofconduct/" rel="noreferrer" target="_blank">http://python.org/psf/codeofconduct/</a><br>
<br>
</span><div class="HOEnZb"><div class="h5">--<br>
<br>
---<br>
You received this message because you are subscribed to a topic in the Google Groups "python-ideas" group.<br>
To unsubscribe from this topic, visit <a href="https://groups.google.com/d/topic/python-ideas/gDc4Ez6Z4MQ/unsubscribe" rel="noreferrer" target="_blank">https://groups.google.com/d/topic/python-ideas/gDc4Ez6Z4MQ/unsubscribe</a>.<br>
To unsubscribe from this group and all its topics, send an email to <a href="mailto:python-ideas%2Bunsubscribe@googlegroups.com">python-ideas+unsubscribe@googlegroups.com</a>.<br>
For more options, visit <a href="https://groups.google.com/d/optout" rel="noreferrer" target="_blank">https://groups.google.com/d/optout</a>.<br>
</div></div></blockquote></div><br></div>