python - 在 Python 中从字典中弹出一个元素的时间复杂度是多少？

Question

这是一道组合数学题。我有一个非常大的列表，all_possible——它存储了所有可能的值——还有一个非常大的dict，present，它存储了所有可能的值实际存在的值，例如:

all_possible = [1, 2, 3, 4, 5]
present = {1: 'some_value', 3: 'some_other_value'}

目前，我的搜索看起来有点像:

for key in all_possible:
    value = present.get(key, None)
    if value is None:
        do_something_if_key_not_present()
    else:
        do_something_if_key_is_present()

这很好用，因为对于每次迭代，字典中只有一次查找，而 Python 字典的平均查找时间 is O(1) .

然而，分摊的最坏情况查找时间是 O(N)，并且由于字典可能非常庞大(数百万个元素)，我考虑过的优化之一涉及在我遍历时从字典中弹出元素(所以后续查找具有更小的搜索空间):

for key in all_possible:
    value = present.pop(key, None)  # this line changes, dict shrinks
    if value is None:
        do_something_if_key_not_present()
    else:
        do_something_if_key_is_present()

我的问题是字典pop的时间复杂度是多少？我知道一般情况下pop操作在像这样的结构中list 是 O(N)，但我找不到任何可靠的文档来说明从 dict 中弹出的复杂性。如果它最终是 O(1)，这可能会加快我的搜索速度，但如果它更高，我可能会伤害自己。

Answer 1

dict.pop的时间复杂度与dict.get的时间复杂度完全一样。 list.pop 是 O(N)，因为它需要移动元素，但 dict.pop 不会那样做。

也就是说，dict.pop 可能不会缩短您的查找时间。从 dict 中删除一个键需要在它的位置留下一个 DKIX_DUMMY 标记，并且查找例程需要将它发现的任何 DKIX_DUMMY 视为哈希冲突，并且继续前进。充其量，您将保存一些 == 对已删除键的比较。

即使 dict.pop 是一项改进，它也不会为您节省 O(N) 最坏情况查找时间。如果您需要处理对抗性的关键选择，dicts 可能不适合您的用例。