[Python-ideas] OrderedDict.peekitem()

[Neil Girdhar]

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.

On Tue, Jul 7, 2015 at 12:15 AM, Andrew Barnert <abarnert at yahoo.com> wrote:

> On Jul 6, 2015, at 15:04, Neil Girdhar <mistersheik at gmail.com> wrote:
>
> You can do indexing, insertion, and removal all in logarithmic time (which
> is basically constant)
>
>
> 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.
>
> 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.
>
> by using a B-tree as the underlying data structure.  (See e.g. the blist
> package.)
>
> On Mon, Jul 6, 2015 at 5:59 PM, Eric Snow <ericsnowcurrently at gmail.com>
> wrote:
>
>> On Mon, Jul 6, 2015 at 3:30 PM, Neil Girdhar <mistersheik at gmail.com>
>> wrote:
>> > SortedDict (
>> http://www.grantjenks.com/docs/sortedcontainers/sorteddict.html)
>> > manages to support indexing.  Can OrderedDict do the same thing?
>>
>> Don't forget that, as the docs describe, an "OrderedDict is a dict
>> that remembers the order that keys were first inserted".  While
>> obviously there's an implicit sequence for that order, the focus is
>> still on dict-ness with the sequence exposed through the normal
>> mapping approach (iteration).  If you want to get sequence semantics
>> then first unpack the order into a sequence type like list or tuple.
>> Or use some other type than OrderedDict.
>>
>> Note that OrderedDict's view types are essentially just dict's view
>> types with custom iteration.  Adding indexing to the views would
>> complicate things and certainly would not be O(1) like you would
>> expect indexing to be.
>>
>> -eric
>>
>
> _______________________________________________
> 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/
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-ideas/attachments/20150707/30b99937/attachment.html>