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

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

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

Answer 1

正如你所说，我猜你必须创建一个数据结构 deque 到 insert/remove 和 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.
也是类似的思路希望对您有所帮助，如果您还有其他问题，请发表评论。 :)

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

How to maintain deque with quick lookup?

python

performance

dictionary

data-structures

deque