[Python-ideas] OrderedDict.peekitem()

[Neil Girdhar]

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.

On Tue, Jul 7, 2015 at 4:33 AM, Masklinn <masklinn at masklinn.net> wrote:

> On 2015-07-07, at 06:23 , Neil Girdhar <mistersheik at gmail.com> wrote:
>
> > 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.
>
> 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).
>
> [0] https://mail.python.org/pipermail/python-dev/2012-December/123028.html
> _______________________________________________
> Python-ideas mailing list
> Python-ideas at python.org
> https://mail.python.org/mailman/listinfo/python-ideas
> Code of Conduct: http://python.org/psf/codeofconduct/
>
> --
>
> ---
> You received this message because you are subscribed to a topic in the
> Google Groups "python-ideas" group.
> To unsubscribe from this topic, visit
> https://groups.google.com/d/topic/python-ideas/gDc4Ez6Z4MQ/unsubscribe.
> To unsubscribe from this group and all its topics, send an email to
> python-ideas+unsubscribe at googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-ideas/attachments/20150707/16c89526/attachment.html>