在 python 中从 python dict
或 defaultdict
中删除一个键是 O(1) 操作,as mentioned here和 here .要从 OrderedDict
中删除键,我们可以使用 del d[key]
或使用 popitem()
方法,如 the docs 中所述。 .
OrderedDict
的底层实现是什么以及del
操作的时间复杂度?
编辑:这个答案 OrderedDict performance (compared to deque) , 指 OrderedDict
中 del
的复杂度为 O(1)。但是,我们如何在实现细节级别证明它的合理性?
最佳答案
implementation Python 3.7 中的 OrderedDict.__delitem__
如下:
def __delitem__(self, key, dict_delitem=dict.__delitem__):
'od.__delitem__(y) <==> del od[y]'
# Deleting an existing item uses self.__map to find the link which gets
# removed by updating the links in the predecessor and successor nodes.
dict_delitem(self, key)
link = self.__map.pop(key)
link_prev = link.prev
link_next = link.next
link_prev.next = link_next
link_next.prev = link_prev
link.prev = None
link.next = None
这段代码做了三件事:
- 从内部键值字典中删除一个项目。
- 从包含链表节点的字典中删除一个节点。
- 从双向链表中删除一个项目。
由于上述所有操作都需要常数时间,因此 OrderedDict.__delitem__
的复杂度也是常数。
关于python - 从 python 有序字典中删除一个键的复杂性,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/51800639/