CODEWITHSUNDEEP
pythondictionarytime-complexity
Héhéhé
Héhéhé

Reputation: 123

How to efficiently get an arbitrary item from a dict?

I am doing some graph theory and I use the NetworkX library.

In some algorithms, one needs to get an arbitrary item from a dictionary to start it (for instance, one of the neighbors of a given node, and the neighborhoods are a dict in NetworkX).

By arbitrary element I mean any element, I don't care which one (not a given element, not a random element, etc.)

Currently I do the following:

D = {i:i**2 for i in range(N)}  # an example of a dictionary where N is a positive integer
any_item_of_D = list(D)[0]      # getting a item of D

But it appears that the time complexity of any_item_of_D = list(D)[0] is linearly growing as N tends to infinity (a O(N) complexity).

Is it possible to get an arbitrary item from a dictionary with a O(1) complexity in Python?

Upvotes: 1

Views: 348

Answers (2)

wim
wim

Reputation: 362557

Pop item returns an arbitrary item in O(1), which you can then put back into the dict (also O(1)).

key, val = D.popitem()
D[key] = val

Since Python 3.7 LIFO order is guaranteed for dict.popitem, so you don't have to worry about it messing up ordering either.

This is significantly faster than creating an item iterator just to get the first item:

>>> timeit k,v = D.popitem(); D[k] = v
107 ns ± 0.0716 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)
>>> timeit next(iter(D.items()))
164 ns ± 0.0687 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)

Note that next(iter(ordered_dict)) is O(1) but next(iter(std_dict)) can be O(n) in worst-case.

Upvotes: 2

Ture Pålsson
Ture Pålsson

Reputation: 6776

I have "always" done next(iter(D.items())), but to be honest, I have never checked whether it is the most efficient way...

Upvotes: 0

Related Questions