在 O(1) 时间内从 python3 dict 中检索任意键

Question

我需要从 python 字典对象中检索任意键。假设我有一本字典d。以下代码的时间复杂度是多少？k = next(iter(d.keys()))我知道在 Python 3 中 d.key() 是 O(1) 时间，next() 是 O(1) 时间。iter() 会发生什么？这可以在不使用额外空间的情况下在 O(1) 时间内完成吗？谢谢！

Answer 1

使用iter（或其他逻辑，例如生成器表达式，声明委托给字典的生成器函数，使用islice等）都是某种形式的包装器，它将.__next__()方法和一些位置簿记添加到对象的视图中next()操作.

这些在很大程度上起作用是因为字典是可迭代的，但没有.__next__()方法，所以iter等人。正在调用该方法，该方法返回一个具有该方法并且是dict 的视图__iter__的可迭代对象。__next__

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

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

---

这是一个演示

首先创建一个相当大的字典（这在慢速系统上可能需要一段时间）

>>> from uuid import uuid4

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

显示这可以直接从现有方法完成

>>> 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'>

这些中的每一个都可以用来读取第一个键

>>> 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'

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

>>> 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

最后，如果需要前 N 个值（而不仅仅是第一个 from ），也可以在循环中有效地调用这些直到达到某个长度或被islicefromitertoolsnext()切片，但是当形成列表等时会产生一些进一步的开销

>>> 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']