如何通过快速查找来维护双端队列？

Question

我需要在 python 中构建一个循环缓冲区作为双端队列，并进行高效搜索（不是 O(n) el in deque，而是像 set() 中那样的 O(1) ）

from collections import deque 
deque = deque(maxlen=10) # in my case maxlen=1000
for i in range(20):
    deque.append(i)
deque 
Out[1]: deque([10, 11, 12, 13, 14, 15, 16, 17, 18, 19])
10 in deque # but it takes O(n), I need O(1)
Out[1]: True

我想我需要维护一个单独的字典来查找，并在双端队列满后从中删除，但不明白如何做。我不需要从双端队列的中间删除，只需像append双端队列那样进行快速查找即可。

Answer 1

正如你所说，我想你必须创建一个数据结构来deque插入/删除并set查找 O(1)，如下所示：

from collections import deque

class CircularBuffer:
    def __init__(self, capacity):
        self.queue = deque()
        self.capacity = capacity
        self.value_set = set()

    def add(self, value):
        if self.contains(value):
            return
        if len(self.queue) >= self.capacity:
            self.value_set.remove(self.queue.popleft())
        self.queue.append(value)
        self.value_set.add(value)

    def contains(self, value):
        return value in self.value_set

测试与输出

cb = CircularBuffer(10)

for i in range(20):
    cb.add(i)

print(cb.queue)
print(cb.contains(10))

# deque([10, 11, 12, 13, 14, 15, 16, 17, 18, 19])
# True

实现一个简单的 LRU Cache + 也是类似的dict想法。 希望对您有帮助，如有其他疑问，请评论。:)double linked list