Как сохранить заказанные уникальные предметы в ограниченных по размеру структурах? - PullRequest
Новая
       49

Как сохранить заказанные уникальные предметы в ограниченных по размеру структурах?

3 голосов
/ 19 сентября 2019

Мне нужно сохранить поток элементов в ограниченном по размеру списке.В потоке могут быть повторяющиеся элементы, но мне нужно просто сохранить уникальные.Также, когда размер моего списка превышает указанное ограничение, мне нужно удалить самый старый элемент и добавить новый.

Я уже пробовал 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]

и set: 

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

Ответы [ 3 ]

1 голос
/ 19 сентября 2019

Возможно, вы захотите изучить использование пакета orderedset.Он доступен через pip или conda.Это очень быстрая библиотека Cpython, которая реализует упорядоченный набор.

pip install orderedset

или 

conda install orderedset -c conda-forge

Вы можете создать подкласс OrderedSet для создания объекта с максимальным количеством элементов. 

from orderedset import OrderedSet

class DequeSet(OrderedSet):
    def __init__(self, *args, maxlen=0, **kwargs):
        if not isinstance(maxlen, int):
            raise TypeError('`maxlen` must be an integer.')
        if not maxlen>=0:
            raise ValueError('`maxlen` must not be negative.')
        self._maxlen = maxlen
        if maxlen:
            args = (args[0][-maxlen:],)
        super().__init__(*args, **kwargs)

    @property
    def maxlen(self):
        return self._maxlen

    def _checkpop(self):
        if not self._maxlen:
            return
        while self.__len__() > self._maxlen:
            self.pop(last=False)

    def __getattr__(self, attr):
        self._checkpop()
        return getattr(self, attr)

# this will truncate to the last 3 elements
ds = DequeSet('abcd', maxlen=3) 
ds 
3 returns:
DequeSet(['b', 'c', 'd'])

ds.add('e')
ds
# returns:
DequeSet(['c', 'd', 'e'])
1 голос
/ 19 сентября 2019

Вы можете написать свой собственный класс, в котором будут установлены обе команды: 

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)
0 голосов
/ 19 сентября 2019

Я создал простую очередь со списком.Также я выстроил условия так, чтобы было меньше сравнений 

class Queue:
  def __init__(self,size):
    self.elements = []
    self.max_size = size

  def put(self,elem):
    if(elem in self.elements):
      return
    elif(len(self.elements) < self.max_size):
      self.elements.append(elem)
    else:
      self.elements = self.elements[1:]+[elem]

  def __str__(self):
    return self.elements.__str__()


q=Queue(3)
q.put(1)
print(q)
q.put(2)
print(q)
q.put(2)
print(q)
q.put(3)
print(q)
q.put(3)
print(q)
q.put(4)
print(q)
...