在O(1)时间内从python3 dict检索任意键 [英] Retrieve an arbitrary key from python3 dict in O(1) time

问题描述

我需要从python字典对象中检索任意键.假设我有一个字典d.以下代码的时间复杂度是多少?

I need to retrieve an arbitrary key from a python dictionary object. Suppose I have a dictionary d. What's the time complexity of the following code?

k = next(iter(d.keys()))

我得到d.key()在Python 3中为O(1)时间，next()在O(1)中. iter()会发生什么? 可以在O(1)时间内完成此操作而不使用额外的空间吗?谢谢！

I get that d.key() is in O(1) time in Python 3, next() is in O(1) time. What happens to the iter()? Can this be done in O(1) time without using extra space? Thanks!

推荐答案

使用iter(或其他逻辑，例如生成器表达式，声明使用islice委托给dict的生成器函数等). )都是某种形式的包装程序，它添加了.__next__()方法，并在操作对象next()的视图中进行了一些位置簿记.

Using iter (or other logic, such as a generator expression, declaring a generator function which delegates to the dict, using islice, etc..) are all some form of wrapper which adds the .__next__() method and some position bookkeeping to the view of the object next() operates on.

这些主要是因为字典都是可迭代的，但没有 .__next__()方法，因此iter等.正在调用__iter__方法，该方法返回一个确实具有__next__方法并且是

These largely work because dicts are iterable, but don't have a .__next__() method, so iter et al. are calling the __iter__ method, which returns an iterable which does have the __next__ method and is a view into the dict.

每种情况都只是O(1)调用的包装，因此一旦声明，它们都将在O(1)时间内运行

Each case is simply a wrapper around an O(1) call, so these will all operate in O(1) time once declared

https://wiki.python.org/moin/TimeComplexity

这是示威游行

首先创建一个可观的字典(在速度较慢的系统上可能需要一段时间)

First create a sizeable dictionary (this may take a while on slow systems)

>>> from uuid import uuid4
>>> d = {str(uuid4()):str(uuid4()) for _ in range(1000000)}

显示此操作可以直接从现有方法完成

Show this can done directly from existing method

>>> next(d.__iter__()
'1273a529-d406-4076-8acc-8993f2613ad4'
>>> type(d.__iter__())
<class 'dict_keyiterator'>

其他对象

>>> n1 = iter(d)          # iter function
>>> n2 = (k for k in d)   # generator expression
>>> def y():              # generator delegation
...   yield from d
...
>>> import itertools
>>> i = itertools.islice(d, 1)  # slice one entry from iterable
>>> type(n1)
<class 'dict_keyiterator'>
>>> type(n2)
<class 'generator'>
>>> type(y())
<class 'generator'>
>>> type(i)
<class 'itertools.islice'>

每一个都可以用来读取第一个键

Each of these can be used to read the first key

>>> next(n1)
'1273a529-d406-4076-8acc-8993f2613ad4'
>>> next(n2)
'1273a529-d406-4076-8acc-8993f2613ad4'
>>> next(y())
'1273a529-d406-4076-8acc-8993f2613ad4'
>>> next(i)
'1273a529-d406-4076-8acc-8993f2613ad4'

证明所有这些都提供了下一个方法

Proof that these have all supplied a next method

>>> dir(d)
['__class__', '__contains__', '__delattr__', '__delitem__', '__dir__', '__doc__', '__eq__', '__format__', '__ge__', '__getattribute__', '__getitem__', '__gt__', '__hash__', '__init__', '__init_subclass__', '__iter__', '__le__', '__len__', '__lt__', '__ne__', '__new__', '__reduce__', '__reduce_ex__', '__repr__', '__setattr__', '__setitem__', '__sizeof__', '__str__', '__subclasshook__', 'clear', 'copy', 'fromkeys', 'get', 'items', 'keys', 'pop', 'popitem', 'setdefault', 'update', 'values']
>>> "__next__" in dir(d)
False
>>> "__next__" in dir(n1)
True
>>> "__next__" in dir(n2)
True
>>> "__next__" in dir(y())
True
>>> "__next__" in dir(i)
True

---

最后，也可以在循环中有效地调用它们，直到达到一定长度或被来自itertools 的islice(如果需要前N个值(而不只是来自next()的第一个))，但是当形成列表或类似内容时会产生一些额外的开销

---

Finally, these can also be efficiently called in a loop until some length is reached or sliced by islice from itertools if the first N values are wanted (rather than just the first from next()), but will incur some further overhead when formed into a list or such

>>> import itertools
>>> list(itertools.islice(d, 5))
['1273a529-d406-4076-8acc-8993f2613ad4', 'a920460d-a193-455c-979c-a91fd700f927', 'aeccb371-43d1-4690-8aaa-d6de0cbe3801', '9aaf2a96-9ef4-4610-8723-8401008e190a', 'e4b450aa-50a2-409a-a5b2-ab88285eb770']

>>> list(itertools.islice(y(), 5))
['1273a529-d406-4076-8acc-8993f2613ad4', 'a920460d-a193-455c-979c-a91fd700f927', 'aeccb371-43d1-4690-8aaa-d6de0cbe3801', '9aaf2a96-9ef4-4610-8723-8401008e190a', 'e4b450aa-50a2-409a-a5b2-ab88285eb770']
>>> list(itertools.islice(n1, 5))
['1273a529-d406-4076-8acc-8993f2613ad4', 'a920460d-a193-455c-979c-a91fd700f927', 'aeccb371-43d1-4690-8aaa-d6de0cbe3801', '9aaf2a96-9ef4-4610-8723-8401008e190a', 'e4b450aa-50a2-409a-a5b2-ab88285eb770']
>>> list(itertools.islice(n2, 5))
['1273a529-d406-4076-8acc-8993f2613ad4', 'a920460d-a193-455c-979c-a91fd700f927', 'aeccb371-43d1-4690-8aaa-d6de0cbe3801', '9aaf2a96-9ef4-4610-8723-8401008e190a', 'e4b450aa-50a2-409a-a5b2-ab88285eb770']

---

另请参见 Python iter()时间复杂度?( snatchysquid对您的回答的第一条评论 >)

---

See also Python iter() time complexity? (first comment on your answer by snatchysquid)

这篇关于在O(1)时间内从python3 dict检索任意键的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！