栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 面试经验 > 面试问答

检查元素是否已在队列中

面试问答 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

检查元素是否已在队列中

标准

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



转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/652408.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号