Python collections.deque双边队列原理详解

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

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

collections.deque

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

deque支持丰富的操作方法，主要方法如图：

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

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

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

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

# 顺时针
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保护下的线程安全方法。

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是原子操作（一行字节码）。

综上，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中则是以返回协程对象的方式执行，具体差异如下表：

  queue.Queue asyncio.Queue
介绍 同步队列 asyncio队列
线程安全 是 否
超时机制 通过timeout参数实现 通过asyncio.wait_for()方法实现
qsize() 预估的队列长度（获取qsize到下一个操作之间，queue有可能被其它的线程修改，导致qsize大小发生变化） 准确的队列长度（由于是单线程，所以queue不会被其它线程修改）
put() / set() put(item, block=True, timeout=None)，可以通过设置block是否为True来配置put和set方法是否为阻塞，并且可以为阻塞操作设置最大时长timeout，block为False时行为和put_nowait()方法一致。 put()方法会返回一个协程对象，所以没有block参数和timeout参数，如果需要非阻塞方法，可以使用put_nowait()，如果需要对阻塞方法应用超时，可以使用coroutine asyncio.wait_for()。

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

总结

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

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。

赞 (0)

相关推荐

  • 简介Python的collections模块中defaultdict类型的用法

    defaultdict 主要用来需要对 value 做初始化的情形.对于字典来说,key 必须是 hashable,immutable,unique 的数据,而 value 可以是任意的数据类型.如果 value 是 list,dict 等数据类型,在使用之前必须初始化为空,有些情况需要把 value 初始化为特殊值,比如 0 或者 ''. from collections import defaultdict person_by_age = defaultdict(list) for pers

  • Python标准库之collections包的使用教程

    前言 Python为我们提供了4种基本的数据结构:list, tuple, dict, set,但是在处理数据量较大的情形的时候,这4种数据结构就明显过于单一了,比如list作为数组在某些情形插入的效率会比较低,有时候我们也需要维护一个有序的dict.所以这个时候我们就要用到Python标准库为我们提供的collections包了,它提供了多个有用的集合类,熟练掌握这些集合类,不仅可以让我们让写出的代码更加Pythonic,也可以提高我们程序的运行效率. defaultdict defaultd

  • Python Deque 模块使用详解

    创建Deque序列: from collections import deque d = deque() Deque提供了类似list的操作方法: d = deque() d.append('1') d.append('2') d.append('3') len(d) d[0] d[-1] 输出结果: 3 '1' '3' 两端都使用pop: d = deque('12345') len(d) d.popleft() d.pop() d 输出结果: 5 '1' '5' deque(['2', '3

  • Python collections.defaultdict模块用法详解

    Python中通过Key访问字典,当Key不存在时,会引发'KeyError'异常.为了避免这种情况的发生,可以使用collections类中的defaultdict()方法来为字典提供默认值. 语法格式: collections.defaultdict([default_factory[, -]]) class defaultdict(Dict[_KT, _VT], Generic[_KT, _VT]): default_factory: Callable[[], _VT] 该函数返回一个类似

  • Python中collections模块的基本使用教程

    前言 之前认识了python基本的数据类型和数据结构,现在认识一个高级的:Collections,一个模块主要用来干嘛,有哪些类可以使用,看__init__.py就知道 '''This module implements specialized container datatypes providing alternatives to Python's general purpose built-in containers, dict, list, set, and tuple. * named

  • python的常用模块之collections模块详解

    认识模块 什么是模块? 常见的场景:一个模块就是一个包含了python定义和声明的文件,文件名就是模块名字加上.py的后缀. 但其实import加载的模块分为四个通用类别:   1 使用python编写的代码(.py文件)   2 已被编译为共享库或DLL的C或C++扩展   3 包好一组模块的包   4 使用C编写并链接到python解释器的内置模块 为何要使用模块? 如果你退出python解释器然后重新进入,那么你之前定义的函数或者变量都将丢失,因此我们通常将程序写到文件中以便永久保存下来,

  • Python collections中的双向队列deque简单介绍详解

    前言 在python神书<Python+Cookbook>中有这么一段话:在队列两端插入或删除元素时间复杂度都是 O(1) ,而在列表的开头插入或删除元素的时间复杂度为 O(N). 于是就想验证下. 简单使用 基本代码 from collections import deque q = deque(maxlen=4)#有固定长度的双向队列 qq = deque() #无固定长度 print(dir(q))#看看有哪些可用方法或属性 结果: ['__add__', '__bool__', '__

  • Python collections模块使用方法详解

    Python collections模块使用方法详解

    一.collections模块 1.函数namedtuple (1)作用:tuple类型,是一个可命名的tuple (2)格式:collections(列表名称,列表) (3)​返回值:一个含有列表的类 (4)例子​: import collections # help(collections.namedtuple) Point = collections.namedtuple("Point",['x','y']) p = Point(15,45) print(p.x+p.y) pri

  • Python collections.deque双边队列原理详解

    队列是一种只允许在一端进行插入操作,而在另一端进行删除操作的线性表. 在Python文档中搜索队列(queue)会发现,Python标准库中包含了四种队列,分别是queue.Queue / asyncio.Queue / multiprocessing.Queue / collections.deque. collections.deque deque是双端队列(double-ended queue)的缩写,由于两端都能编辑,deque既可以用来实现栈(stack)也可以用来实现队列(queue

  • python装饰器的特性原理详解

    这篇文章主要介绍了python装饰器的特性原理详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 今天发现了装饰器的另一种用法,下面就先上代码: data_list = [] def data_item(func): data_list.append(func) return func @data_item def foo(): return 1 @data_item def foo1(): return 2 @data_item def fo

  • Python JSON编解码方式原理详解

    Python JSON编解码方式原理详解

    这篇文章主要介绍了Python JSON编解码方式原理详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 概念 JSON(JavaScript Object Notation) 是一种轻量级的数据交换格式,易于人阅读和编写.在日常的工作中,应用范围极其广泛.这里就介绍python下它的两种编解码方法: 使用json函数 使用 JSON 函数需要导入 json 库:import json.函数含义: 源码解析: # coding= utf-8 #

  • Python学习之直方图均衡化原理详解

    Python学习之直方图均衡化原理详解

    目录 1.点算子 2.线性灰度变换 3.直方图均衡化 4.代码实战 1.点算子 点算子是两个像素灰度值间的映射关系,属于像素的逐点运算,相邻像素不参与运算.点算子是最简单的图像处理手段,如:亮度调整.对比度调整.颜色变换.直方图均衡化等等. 2.线性灰度变换 线性灰度变换表达为: 其中rk.sk分别为输入.输出点像素灰度值. ▲图2.1 线性灰度变换 当a>1时,输出图像像素灰度范围扩大,图像对比度增强,当a<1时反之.这是因为人眼不易区分相近的灰度值,因此若图像灰度值范围较小,观感上细节不够

  • python神经网络Batch Normalization底层原理详解

    python神经网络Batch Normalization底层原理详解

    目录 什么是Batch Normalization Batch Normalization的计算公式 Bn层的好处 为什么要引入γ和β变量 Bn层的代码实现 什么是Batch Normalization Batch Normalization是神经网络中常用的层,解决了很多深度学习中遇到的问题,我们一起来学习一哈. Batch Normalization是由google提出的一种训练优化方法.参考论文:Batch Normalization Accelerating Deep Network T

  • Python进程间通信 multiProcessing Queue队列实现详解

    一.进程间通信 IPC(Inter-Process Communication) IPC机制:实现进程之间通讯 管道:pipe 基于共享的内存空间 队列:pipe+锁的概念--->queue 二.队列(Queue) 2.1 概念-----multiProcess.Queue 创建共享的进程队列,Queue是多进程安全的队列,可以使用Queue实现多进程之间的数据传递. Queue([maxsize])创建共享的进程队列. 参数 :maxsize是队列中允许的最大项数.如果省略此参数,则无大小限制

  • Python线程障碍对象Barrier原理详解

    python线程Barrier俗称障碍对象,也称栅栏,也叫屏障. 一.线程障碍对象Barrier简介 # 导入线程模块 import threading # 障碍对象barrier barrier = threading.Barrier(parties, action=None, timeout=None) parties - 线程计数器,记录线程数量,也称线程障碍数量: action - 是一个可调用函数,当等待的线程到达了线程障碍数量parties,其中一个线程会首先调用action 对应函

  • Python中的延迟绑定原理详解

    直接看下面例子 my_ld = [lambda x:x*i for i in range(3)] my_list = [ld(2) for ld in my_ld] print(my_list) 本想是想通过以上代码,输出[0, 2, 4]的,但结果却是[4, 4, 4] 下面说下本人对这个结果的理解: 因为Python解释器,遇到lambda(或者def),只是定义了一个匿名函数对象,并保存在内存中,只有等到调用这个匿名函数的时候,才会执行函数内部的代码(x*i).所以匿名函数中的i并不是立即

  • Python作用域与名字空间原理详解

    Python具有静态作用域,变量的作用域由它定义的位置决定,而与调用的位置无关. a = 2  def f():  a = 2 第一行的a的作用域是全局作用域,作用于定义位置后面的所有位置. 第四行的a的作用域是局部作用域,作用于f函数里. Python能够形成局部作用域的只有函数与类,其他语句不形成局部作用域. 函数与类的局部作用域 def f(): a = 1 class A: b = 2 if 1 == 1: c = 3 for _ in range(1): d = 4 while Tru

  • Python基于class()实现面向对象原理详解

    首先,类是一个集合,包含了数据,操作描述的一个抽象集合 你可以首先只把类当做一个容器来使用 class Cycle: def __init__(self,r): self.pi=3.14 self.r=r a=Cycle(4) b=Cycle(7) 你看,我们定义了一个 Cycle 类,我们现在只是将它当做一个数据集合来用,我们利用其实例之间彼此数据隔离的特性来保证具体的实例数据彼此不污染.好了你现在想问,为什么我们要用数据集合来放数据 好了,我们来看看没有类之前我们会怎么样,假设我们现在要计算

随机推荐