在Python中从dict弹出元素的时间复杂度是多少？

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字典的平均查找时间是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像listO(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可能不适合您的用例.