从python有序字典中删除键的复杂性 [英] Complexity of deleting a key from python ordered dict

问题描述

在python中从python dict 或 defaultdict 删除键是O（1）操作，如此处所述和此处。要从 OrderedDict 中删除​​键，我们可以使用 del d [key] 或使用 popitem（）方法，如文档。

Deleting a key from a python dict or defaultdict in python is O(1) operation, as mentioned here and here. To remove a key from OrderedDict, we can either use del d[key] or use popitem() method, as mentioned in the docs.

OrderedDict 的基本实现是什么，<$ c的时间复杂度$ c> del 操作？

What is the underlying implementation of OrderedDict and the time complexity of del operation?

编辑：此答案 OrderedDict性能（与deque相比），是指 OrderedDict 为O（1）。但是，我们如何才能在实现详细信息级别证明其合理性呢？

This answer OrderedDict performance (compared to deque) , refers to the complexity of del in OrderedDict as being O(1). However, how can we justify it at implementation detail level?

推荐答案

OrderedDict .__ delitem __ 的/python/cpython/blob/3.7/Lib/collections/__init__.py#L129 rel = noreferrer>实现如下所示：

The implementation of OrderedDict.__delitem__ in Python 3.7 is as follows:

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

此代码执行3件事：

• 从内部键值字典中删除一项。


• 从包含链接列表节点的字典中删除一个节点。


• 从双向链接列表中删除一个项目。

由于上述所有操作都需要花费固定的时间，因此 OrderedDict .__ delitem __ 的复杂度也是恒定的。

Since all of the operations above take constant time, the complexity of OrderedDict.__delitem__ is constant as well.

这篇关于从python有序字典中删除键的复杂性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！