Retrieve An Arbitrary Key From Python3 Dict In O(1) Time

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())) I ge

Solution 1:

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.

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.

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

---

Here's a demonstration

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

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

Show this can done directly from existing method

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

Further objects

>>> n1 = iter(d)          # iter function>>> n2 = (k for k in d)   # generator expression>>> defy():              # generator delegation... yieldfrom 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__"indir(d)
False>>> "__next__"indir(n1)
True>>> "__next__"indir(n2)
True>>> "__next__"indir(y())
True>>> "__next__"indir(i)
True

---

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

---

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