Python中的双端队列

前言

本文主要介绍Python中的双端队列deque,具体会介绍:

  1. 什么是双端列表?
  2. Python列表与双端列表
  3. 双端列表的使用

a 什么是双端队列?

deque的英文意思是Double-Ended Queue,从字面的意思来看,他就是一个双向队列。我们使用list存储数据的时候,按索引访问元素很快,因为list是线性存储,数据量很大的时候在列表头插入和删除元素的效率就会很慢。为什么list效率低呢?

  • 因为list有append()和insert(index,value)两个添加方法,append()方法只能在在列表的尾部追加元素,而insert(index)虽然能在指定的位置去添加元素,但是他需要去遍历list才行所以时间复杂度为o(N)。
  • 而list中的删除有del names[index],pop()或者pop(index),remove(value)可以看出list删除除了pop()[删除列表末尾的元素]之外,剩下的都需要去遍历list列表,所以时间复杂度是o(N)。

deque是为了在两端高效实现插入和删除操作的双向列表,适合用于队列和栈:deque除了实现list的append()和pop()外,还支持appendleft()和popleft(),这样就可以非常高效地往头部或者尾部添加或删除元素。

b 列表与双端队列

双端队列支持线程安全,在双端队列的任何一端执行添加和删除操作,它们的内存效率几乎相同(时间复杂度为O(1))。 虽然list也支持类似的操作,但是它对定长列表的操作表现很不错,而当遇到pop(0)和insert(0, v)这样既改变了列表的长度又改变其元素位置的操作时,其时间复杂度就变为O(n)了。 在双端队列中最好不使用切片(如果使用deque进行切片的话会抛出异常)和索引(和列表一样的使用,虽然效果上是一样的,但是可能效率上还是列表的索引效率更高一些),你可以用popleft和appendleft方法,双端队列对这些操作做了优化。在两端的索引访问时间复杂度为O(1),但是访问中间元素的时间复杂度为O(n),速度较慢,对于快速随机的访问,还是用列表代替。 列表用于随机访问和定长数据的操作,包括切片,而双端队列适用于在两端压入或弹出元素,索引的效率可能低于列表,同时也不支持切片。

c 双端队列的使用

▲deque队列中的函数

extendleft()方法,他是把列表中的元素进行迭代,先取出第一个元素,然后放在左边,然后再去取出下一个,重复执行,就得到了最终的结果。

from collections import deque
d = deque([1,2,3])
d.extendleft(['a','b','c'])
print(d)

deque(['c', 'b', 'a', 1, 2, 3])

其他类似list的操作方法

from collections import deque
d = deque(['a','b','c','d','e','f'])
print(d)
print(len(d))#获取双端队列的长度
print(d[-1])#类似list的索引访问,使用方法与列表的索引一样
# d.reverse()
# print(d)#反转输出
print(d.count('a'))#输出元素出现的次数
print(d.index('e'))
print(d.index('c',0,3))  #指定查找区间
#插入元素
d.insert(0,1)
print(d)
#remove(value)
#删除指定元素
d.remove('a')
print(d)

deque(['a', 'b', 'c', 'd', 'e', 'f'])
6
f
1
4
2
deque([1, 'a', 'b', 'c', 'd', 'e', 'f'])
deque([1, 'b', 'c', 'd', 'e', 'f'])

注意:如果使用deque进行切片的话会抛出异常

TypeError: sequence index must be integer, not 'slice',中文翻译的意思就是:类型错误:序列索引必须是整数,而不是“切片”。

from collections import deque
d = deque([1,2,3,4])
print(d[:-1])

Traceback (most recent call last):
  File "G:/Python源码/dequetest.py", line 3, in <module>
    print(d[:-1])
TypeError: sequence index must be integer, not 'slice'

rotate(把右边元素放到左边,默认为1)

from collections import deque
d = deque([1,2,3,4,5])
d.rotate()#默认为1
d.rotate(1)
print(d)

deque([5, 1, 2, 3, 4])

参数>0的时候是从右往左放元素

from collections import deque
d = deque([1,2,3,4,5])
d.rotate(2)
print(d)

deque([4, 5, 1, 2, 3])

参数<0的时候是从左往右放元素

from collections import deque
d = deque([1,2,3,4,5])
d.rotate(-2)
print(d)

deque([3, 4, 5, 1, 2])

还有一个值得关注的地方,初始化deque的时候可以给他传一个参数maxlen,如果deque中的元素超过maxlen的值,那么就会从deque中的一边去删除元素,也就是deque始终保持maxlen最大长度的元素,如果超过了就会自动把以前的元素弹出(删除)。当然这些追加都是没有问题的。

from collections import deque
d = deque([1,2,3],maxlen = 3)
print(d)
d.append(4)
print(d)
d.appendleft(5)
print(d)

deque([1, 2, 3], maxlen=3)
deque([2, 3, 4], maxlen=3)
deque([5, 2, 3], maxlen=3)

当时如果我使用insert(index,value)就会抛出异常。当然这种情况出现在我队列中的元素==maxlen的情况下使用insert才会抛出异常。如果元素!=maxlen的时候insert没有问题。我觉得可能在指定位置插入的话,他不知道去删除那一端的元素。

from collections import deque
d = deque([1,2,3],maxlen = 3)
# d.insert(0,'a')
# print(d)
d.insert(1,'b')
print(d)

Traceback (most recent call last):
  File "G:/Python源码/collections_deque.py", line 5, in <module>
    d.insert(1,'b')
IndexError: deque already at its maximum size

当然删除操作肯定不会有什么问题。

from collections import deque
d = deque([1,2,3],maxlen = 3)
print(d)
d.pop()
print(d)
d.popleft()
print(d)
d.remove(2)
print(d)

deque([1, 2, 3], maxlen=3)
deque([1, 2], maxlen=3)
deque([2], maxlen=3)
deque([], maxlen=3)

本文分享自微信公众号 - AI机器学习与深度学习算法(AI-KangChen),作者:Chenkc

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-04-17

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 机器学习入门 9-7 scikit-learn中的逻辑回归

    本系列是《玩转机器学习教程》一个整理的视频笔记。本小节主要介绍使用sklearn实现逻辑回归算法以及添加多项式项的逻辑回归算法,sklearn为逻辑回归自动封装...

    触摸壹缕阳光
  • 数据结构与算法 1-3 最坏时间复杂度与计算规则

    本系列是我在学习《基于Python的数据结构》时候的笔记。本小节主要介绍算法时间复杂度的三种不同程度:最坏时间复杂度、最优时间复杂度以及平均时间复杂度,并且介绍...

    触摸壹缕阳光
  • 数据结构与算法 1-4 常见时间复杂度与大小关系

    本系列是我在学习《基于Python的数据结构》时候的笔记。本小节主要介绍一些常见的时间复杂度以及它们之间的大小关系。

    触摸壹缕阳光
  • Python列表与deque的区别

    青南
  • 一文了解STL容器deque类

    双端队列底层是一段假象的连续空间,实际是分段连续的,为了维护其“整体连续”的假象,落在了deque的迭代器身上。

    海盗船长
  • 3 . python Collectio

    class collections.deque([iterable[, maxlen]])

    py3study
  • python双端队列deque

    由于deque是一种序列容器,因此同样支持list的一些操作,如用getitem()检查内容,确定长度,以及通过匹配标识从序列中间删除元素。

    用户2936342
  • 扯一扯HTTPS单向认证、双向认证、抓包原理、反抓包策略

    HTTP(HyperText Transfer Protocol,超文本传输协议)被用于在Web浏览器和网站服务器之间传递信息,在TCP/IP中处于应用层。这里...

    Android技术干货分享
  • 谈谈HTTPS安全认证,抓包与反抓包策略

    协议是指计算机通信网络中两台计算机之间进行通信所必须共同遵守的规定或规则,超文本传输协议(HTTP)是一种通信协议,它允许将超文本标记语言(HTML)文档从We...

    逆月翎
  • IBM研究者开发Game Boy超级计算机,每秒处理十亿帧

    机器学习算法能够在我们最艰难的棋盘游戏,经典视频游戏甚至一些现代游戏中胜过人类。但它们仍然有一些很大的局限性,主要与记忆有关,或者更确切地说,它缺乏记忆。

    AiTechYun

扫码关注云+社区

领取腾讯云代金券