详解Python中的四种队列

时间:2022-08-23 19:00:06

队列是一种只允许在一端进行插入操作,而在另一端进行删除操作的线性表。

在python文档中搜索队列(queue)会发现,python标准库中包含了四种队列,分别是queue.queue / asyncio.queue / multiprocessing.queue / collections.deque。

collections.deque

deque是双端队列(double-ended queue)的缩写,由于两端都能编辑,deque既可以用来实现栈(stack)也可以用来实现队列(queue)。

deque支持丰富的操作方法,主要方法如图:

详解Python中的四种队列

相比于list实现的队列,deque实现拥有更低的时间和空间复杂度。list实现在出队(pop)和插入(insert)时的空间复杂度大约为o(n),deque在出队(pop)和入队(append)时的时间复杂度是o(1)。

deque也支持in操作符,可以使用如下写法:

?
1
2
3
q = collections.deque([1, 2, 3, 4])
print(5 in q) # false
print(1 in q) # true

deque还封装了顺逆时针的旋转的方法:rotate。

?
1
2
3
4
5
6
7
8
9
10
11
12
# 顺时针
q = collections.deque([1, 2, 3, 4])
q.rotate(1)
print(q) # [4, 1, 2, 3]
q.rotate(1)
print(q) # [3, 4, 1, 2]
# 逆时针
q = collections.deque([1, 2, 3, 4])
q.rotate(-1)
print(q) # [2, 3, 4, 1]
q.rotate(-1)
print(q) # [3, 4, 1, 2]

线程安全方面,collections.deque中的append()、pop()等方法都是原子操作,所以是gil保护下的线程安全方法。

?
1
2
3
4
5
6
7
static pyobject *
deque_append(dequeobject *deque, pyobject *item) {
 py_incref(item);
 if (deque_append_internal(deque, item, deque->maxlen) < 0)
 return null;
 py_return_none;
}

通过dis方法可以看到,append是原子操作(一行字节码)。

详解Python中的四种队列

综上,collections.deque是一个可以方便实现队列的数据结构,具有线程安全的特性,并且有很高的性能。

queue.queue & asyncio.queue

queue.queue和asyncio.queue都是支持多生产者、多消费者的队列,基于collections.deque,他们都提供了queue(fifo队列)、priorityqueue(优先级队列)、lifoqueue(lifo队列),接口方面也相同。

区别在于queue.queue适用于多线程的场景,asyncio.queue适用于协程场景下的通信,由于asyncio的加成,queue.queue下的阻塞接口在asyncio.queue中则是以返回协程对象的方式执行,具体差异如下表:

详解Python中的四种队列

multiprocessing.queue

multiprocessing提供了三种队列,分别是queue、simplequeue、joinablequeue。

详解Python中的四种队列

multiprocessing.queue既是线程安全也是进程安全的,相当于queue.queue的多进程克隆版。和threading.queue很像,multiprocessing.queue支持put和get操作,底层结构是multiprocessing.pipe。

multiprocessing.queue底层是基于pipe构建的,但是数据传递时并不是直接写入pipe,而是写入进程本地buffer,通过一个feeder线程写入底层pipe,这样做是为了实现超时控制和非阻塞put/get,所以queue提供了join_thread、cancel_join_thread、close函数来控制feeder的行为,close函数用来关闭feeder线程、join_thread用来join feeder线程,cancel_join_thread用来在控制在进程退出时,不自动join feeder线程,使用cancel_join_thread有可能导致部分数据没有被feeder写入pipe而导致的数据丢失。

和threading.queue不同的是,multiprocessing.queue默认不支持join()和task_done操作,这两个支持需要使用mp.joinablequeue对象。

simplequeue是一个简化的队列,去掉了queue中的buffer,没有了使用queue可能出现的问题,但是put和get方法都是阻塞的并且没有超时控制。

总结

通过对比可以发现,上述四种结构都实现了队列,但是用处却各有偏重,collections.deque在数据结构层面实现了队列,但是并没有应用场景方面的支持,可以看做是一个基础的数据结构。queue模块实现了面向多生产线程、多消费线程的队列,asyncio.queue模块则实现了面向多生产协程、多消费协程的队列,而multiprocessing.queue模块实现了面向多成产进程、多消费进程的队列。

以上所述是小编给大家介绍的python中的四种队列,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对服务器之家网站的支持!

原文链接:https://juejin.im/post/5b022e456fb9a07aaf35810d