16

我Queue在 python 中使用该库，我想保持队列条目的唯一性。

因此，我想在添加到队列之前检查“某物”是否已经在队列中，本质上是一个在队列库上工作的函数：

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

或者，我应该使用不同的库/方法来实现这一点吗？

4

1 回答 1

51

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

于 2013-05-12T10:44:40.927 回答