[Python-ideas] OrderedDict.peekitem()

[Andrew Barnert]

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/20150706/dbda63c9/attachment.html>