Как сохранить deque с помощью быстрого поиска? - PullRequest
Новая
       41

Как сохранить deque с помощью быстрого поиска?

3 голосов
/ 06 мая 2019

Мне нужно построить кольцевой буфер как deque в Python с эффективным поиском (не O (n) el in deque, а O (1), как в set ()) 

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, как это сделал deque и быстрый поиск.

1 Ответ

2 голосов
/ 06 мая 2019

Как вы сказали, я полагаю, вам нужно создать структуру данных с 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.
Надеюсь, что это поможет вам, и прокомментируйте, если у вас есть дополнительные вопросы. :)

...