检查元素是否已在队列中

Question

我正在Queuepython中使用该库，并且希望保持队列条目唯一。

因此，我想在添加到队列之前检查队列中是否没有“某物”，本质上是这样的函数，它可以在队列库中工作：

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（类似于OrderedDictin
collections）解决此问题。文档链接了一个食谱collections。一旦拥有了：

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则是一种更好的方法。