python - 如何在尺寸有限的结构中保存有序的独特元素？

Question

我需要将元素流保存在一个大小有限的列表中。流中可能有重复的元素，但我只需要保留唯一的元素。此外，当列表的大小超过指定限制时，我需要删除最旧的元素并添加新元素。

我已经尝试过set 和list。 set 的问题是它没有大小限制，如果我想删除最旧的元素，我不知道如何检索它，因为 set 是无序的；但是，它解决了唯一性问题。

另一方面，list 保持项目的顺序，但每当我想插入一个新元素时，我都需要检查可能的重复项，这会花费很多时间。此外，list 和 set 一样不受大小限制。

我的第三个选项可能是 collections.deque 但我不知道它是否保持顺序。有没有办法让 collections.deque 中的项目保持唯一？

这些是我的 list 代码示例:

ids = list()
for item in stream:
    if item not in ids:
        ids.append(item)
    if len(ids) >= len_limit:
        del ids[0]

和设置:

ids = set()
for item in stream:
    ids.add(item)
    if len(ids) >= len_limit:
        ids.remove(list(ids)[0])

Answer 1

您可以编写自己的类，同时保留 deque 和 set:

import collections


class Structure:
    def __init__(self, size):
        self.deque = collections.deque(maxlen=size)
        self.set = set()

    def append(self, value):
        if value not in self.set:
            if len(self.deque) == self.deque.maxlen:
                discard = self.deque.popleft()
                self.set.discard(discard)
            self.deque.append(value)
            self.set.add(value)

s = Structure(2)
s.append(1)
s.append(2)
s.append(3)
s.append(3)
print(s.deque)  # deque([2, 3], maxlen=2)