检查元素是否已在队列中

Question

我Queue在python中使用库,我想保持队列条目的唯一性.

因此我想在添加它之前检查队列中是否还没有'某事',本质上是一个在Queue库上工作的函数:

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