简析Python中的四种队列

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

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

01

collections.deque

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

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

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

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

1q = collections.deque([1, 2, 3, 4])
2print(5 in q)  # False
3print(1 in q)  # True

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

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

线程安全方面,通过查看collections.deque中的append()、pop()等方法的源码可以知道,他们都是原子操作,所以是GIL保护下的线程安全方法。

1static PyObject *
2deque_append(dequeobject *deque, PyObject *item) { 
3    Py_INCREF(item);
4    if (deque_append_internal(deque, item, deque->maxlen) < 0) 
5        return NULL;
6    Py_RETURN_NONE;
7}

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

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

02

queue.Queue & asyncio.Queue

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

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

03

multiprocessing.Queue

multiprocessing提供了三种队列,分别是Queue、SimpleQueue、JoinableQueue。

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方法都是阻塞的并且没有超时控制。

04

总结

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

05

参考

https://docs.python.org/3/library/collections.html#collections.deque https://docs.python.org/3/library/queue.html https://docs.python.org/3/library/asyncio-queue.html https://docs.python.org/3/library/multiprocessing.html#multiprocessing.Queue https://bugs.python.org/issue15329 http://blog.ftofficer.com/2009/12/python-multiprocessing-3-about-queue/ http://cyrusin.github.io/2016/04/27/python-gil-implementaion/

原文发布于微信公众号 - Python私房菜(python-fans)

原文发表时间:2018-05-21

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏陈树义

Java并发编程:线程控制

在上一篇文章中(Java并发编程:线程的基本状态)我们介绍了线程状态的 5 种基本状态以及线程的声明周期。这篇文章将深入讲解Java如何对线程进行状态控制,比如...

4079
来自专栏对角另一面

lodash源码分析之Hash缓存

在那小小的梦的暖阁,我为你收藏起整个季节的烟雨。 ——洛夫《灵河》 本文为读 lodash 源码的第四篇,后续文章会更新到这个仓库中,欢迎 star:poc...

3429
来自专栏java学习

1.3java的运行原理

java的运行原理 这里我们简单分析一下我们的第一个应用程序,其中涉及到很多没有接触过的概念,大家可先阅读以下,以后会详细讲解。重点是理解java的运行原理。 ...

3654
来自专栏码洞

深度学习Java之内存模型【译】

Java的内存模型定义了Java虚拟机如何和计算机物理内存进行交互。Java虚拟机是一体化的计算机模型,所以它自然也包含了内存模型。

841
来自专栏我是攻城师

理解Java里面的代理模式

代理模式是23种设计模式中非常经典的一种模式,在日常生活中到处充满了代理模式的痕迹,常见的比如火车代售点买票,各种公共服务大厅,以及各种网上购物平台其实都可以看...

4361
来自专栏Janti

Java多线程高并发学习笔记(一)——Thread&Runnable

 进程与线程 首先来看百度百科关于进程的介绍: 进程是一个具有独立功能的程序关于某个数据集合的一次运行活动。它可以申请和拥有系统资源,是一个动态的概念,是一个活...

74810
来自专栏屈定‘s Blog

Java学习记录--委派模型与类加载器

最近在读许令波的深入分析Java Web技术内幕一书,对于学习Java以来一直有的几个疑惑得到了解答,遂记录下来.

1587
来自专栏Java架构师历程

JVM加载class文件的原理

当Java编译器编译好.class文件之后,我们需要使用JVM来运行这个class文件。那么最开始的工作就是要把字节码从磁盘输入到内存中,这个过程我们叫做【加载...

5242
来自专栏Android 研究

Java虚拟机基础——2JVM运行时数据区

本篇文章主要讲解JVM运行时数据区,所以我们按照线程是否私有的维度将本篇文章一分为二,分为线程私有数据区和所有线程共有的数据区。而在线程私有的数据区又可以分为程...

1365
来自专栏栗霖积跬步之旅

java多线程编程核心技术——第二章总结

第一节synchronized同步方法目录 1.1方法内的变量为线程安全的 1.2实例变量非线程安全 1.3多个对象多个锁 1.4synch...

21510

扫码关注云+社区

领取腾讯云代金券