如何有效地从字典中获取任意项目？

Question

我正在研究一些图论，我使用 NetworkX 库。

在某些算法中，需要从字典中获取任意项才能启动它（例如，给定节点的邻居之一，而邻居是 NetworkX 中的字典）。

通过任意元素我的意思是任何元素，我不关心是哪个（不是给定元素，不是随机元素等）

目前我在做以下事情：

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

但是随着 N 趋于无穷大（O(N) 复杂度），any_item_of_D = list(D)[0] 的时间复杂度似乎呈线性增长。

是否可以在 Python 中从具有 O(1) 复杂度的字典中获取任意项？

Answer 1

弹出项目 returns O(1) 中的任意项目，然后您可以将其放回字典中（也 O(1 )).

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

自 Python 3.7 LIFO order is guaranteed 以来 dict.popitem，因此您不必担心它会弄乱排序。

这比仅仅为了获取第一个项目而创建项目迭代器要快得多：

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

请注意 next(iter(ordered_dict)) 是 O(1) 但 next(iter(std_dict)) can be O(n) in worst-case.

Answer 2

我“总是”这样做next(iter(D.items()))，但老实说，我从来没有检查过它是否是最有效的方法...

如何有效地从字典中获取任意项目？

How to efficiently get an arbitrary item from a dict?

python

dictionary

time-complexity