Проверьте, находится ли элемент в очереди

Question

Я использую Queue библиотека в Python, и я хочу, чтобы записи в очереди были уникальными.

Поэтому я хочу проверить, что "что-то" еще не находится в очереди, прежде чем добавить к нему, по сути, такую ​​функцию, которая работает в библиотеке очереди:

queue = Queue.Queue()
def in_queue(u):
  return u in queue

Или я должен использовать другую библиотеку / метод для достижения этой цели?

Answer 1

Стандарт Queue класс не может быть повторен или проверен иным образом.

Тем не менее, он был построен для расширения.

Во-первых, если вы посмотрите на источник (который связан с документами), есть методы ловушки _init, _qsize, _put а также _get что вы можете изменить, чтобы изменить реализацию. Посмотрите на подклассы ниже основного класса, и вы увидите, как они это делают.

Итак, одна простая вещь, чтобы сделать, это заменить deque реализация с set:

class SetQueue(Queue.Queue):
    def _init(self, maxsize):
        self.queue = set()
    def _put(self, item):
        self.queue.add(item)
    def _get(self):
        return self.queue.pop()

(Я не реализовал _qsize потому что по умолчанию return len(self.queue) Это хорошо.)

Теперь вам не нужно проверять, просто добавьте его в очередь, и он будет игнорироваться, если он уже есть.

Конечно, это имеет обратную сторону: очередь больше не упорядочена. Но вы можете решить это с помощью OrderedSet (аналогично OrderedDict в collections). Есть рецепт, который связан с collections Docs. Как только у вас есть это:

class OrderedSetQueue(Queue.Queue):
    def _init(self, maxsize):
        self.queue = OrderedSet()
    def _put(self, item):
        self.queue.add(item)
    def _get(self):
        return self.queue.pop()

---

Если вы действительно хотите иметь возможность проверять значения в очереди, вы можете добавить метод для этого:

class CheckableQueue(Queue.Queue): # or OrderedSetQueue
    def __contains__(self, item):
        with self.mutex:
            return item in self.queue

Тем не менее, это предлагает условия гонки в вашем коде. Например, если вы делаете это:

if x not in my_queue:
    my_queue.put(x)

Всегда возможно, что x не был в очереди, когда вы проверяли, но был в очереди, когда вы звонили put, Фактически, единственное использование этой функции, которое не было бы небезопасным, - это какая-то оптимистическая проверка (если значение не находится в очереди сейчас, сделайте некоторую дорогую работу, затем попробуйте добавить ее, принимая, что работа потрачена впустую если значение было добавлено в то же время) - та же причина Queue.full() существует.

Единственный способ сделать это безопасно - объединить обе операции под замком:

with my_queue.mutex:
    if x not in my_queue:
        my_queue.put(x)

Но на этом этапе вы побеждаете цель использования Queue на первом месте. (Вы также в зависимости от того, что Queue.mutex является рекурсивно-вводимым мьютексом. Лучше добавить операцию как метод вашего Queue подкласс.

И если вы всегда хотите сначала проверить и добавить, только если его там нет, OrderedSetQueue это лучший способ сделать это.