时间戳

首页 > 解决方案 > 在 O(1) 中删除 deque 中的散列节点

python - 在 O(1) 中删除 deque 中的散列节点

问题描述

如何在 deque 中散列一个内置节点（这是一个双链表）并在 O(1) 中删除中间的节点？内置节点是否暴露？

例如，我想将一个双端队列的节点保存在 dict 中，以便以后可以在恒定时间内删除该节点。

这是 LRU 中的一个用例，使用 deque，所以我不需要编写自己的双链表。

from collections import deque

class LRU:
  def __init__(self):
    self.nodes = deque()
    self.key2node = {}

  def insertThenDelete(self):
    # insert
    node = deque.Node('k', 'v') # imagine you can expose deque node here
    self.nodes.appendleft(node) 
    self.key2node = {'k': node} 

    # delete
    self.key2node['k'].deleteInDeque() # HERE shold remove the node in DLL!
    del self.key2node['k']

我知道你可以del mydeque[2]按索引删除。但我想key2node['k'].deleteInDeque()通过引用进行删除。

标签： pythondequepython-internals

解决方案

deque API 不支持直接引用内部节点或直接删除内部节点，因此您尝试执行的操作对于collections.deque()是不可能的。

此外，双端队列实现是一个固定长度块的双向链表，其中一个块位于对象指针数组中，因此即使您可以获得引用，也没有简单的方法来删除块的一部分（它是固定长度）。

最好的办法是从头开始创建自己的双向链表。请参阅 functools.lru_cache() 的源代码，它完全符合您的描述： https ://github.com/python/cpython/blob/3.7/Lib/functools.py#L405

希望这可以帮助 ：-）

推荐阅读