mistersheik at gmail.com
Tue Jul 7 10:37:00 CEST 2015
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 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).
>  https://mail.python.org/pipermail/python-dev/2012-December/123028.html
> Python-ideas mailing list
> Python-ideas at python.org
> 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
> 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...
More information about the Python-ideas