deque对象-collections- 容器数据类型(29)Python语言(必读进阶学习教程)(参考资料)
- class
collections.
deque
([ iterable [,maxlen ] ] ) - 返回一个从左到右(使用
append()
)初始化的新deque对象,其中包含来自iterable的数据。如果未指定iterable,则新的deque为空。Deques是堆栈和队列的概括(名称发音为“deck”,是“双端队列”的缩写)。Deques支持线程安全,内存有效的附加和从双端队列的弹出,在任一方向上具有大致相同的O(1)性能。
尽管
list
对象支持类似的操作,但它们针对快速固定长度操作进行了优化,并且导致O(n)内存移动成本pop(0)
和操作,这些成本 改变了底层数据表示的大小和位置。insert(0, v)
如果未指定maxlen
None
,则deques可能会增长到任意长度。否则,双端队列限制为指定的最大长度。一旦有界长度双端队列已满,当添加新项目时,从对方端丢弃相应数量的项目。有界长度deques提供类似于tail
Unix中的过滤器的功能。它们还可用于跟踪仅涉及最近活动的事务和其他数据池。Deque对象支持以下方法:
append
(x )- 将x添加到双端队列的右侧。
appendleft
(x )- 将x添加到双端队列的左侧。
clear
()- 删除deque中的所有元素,使其长度为0。
copy
()- 创建双端队列的浅表副本。
版本3.5中的新功能。
count
(x )- 计算deque元素的数量等于x。
版本3.2中的新功能。
extend
(可迭代的)- 通过附加可迭代参数中的元素来扩展双端队列的右侧。
extendleft
(可迭代的)- 通过附加来自iterable的元素来扩展双端队列的左侧。注意,左边追加的系列会导致反转迭代参数中元素的顺序。
index
(x [,start [,stop ] ] )- 返回deque 中x的位置(在索引开始时或 索引停止之前)。返回第一个匹配或
ValueError
如果未找到则引发 。版本3.5中的新功能。
insert
(i,x )- 将x插入位置i的双端队列中。
如果插入会导致有界双端超过maxlen,
IndexError
则会引发a。版本3.5中的新功能。
pop
()- 从双端队列的右侧移除并返回一个元素。如果没有元素,则提出一个
IndexError
。
popleft
()- 从双端队列的左侧移除并返回一个元素。如果没有元素,则提出一个
IndexError
。
remove
(值)- 删除第一次出现的值。如果没有找到,提出一个
ValueError
。
reverse
()- 在原位反转deque的元素然后返回
None
。版本3.2中的新功能。
rotate
(n = 1 )- 向右旋转deque n步。如果n为负数,则向左旋转。
当双端队列不为空时,向右
d.appendleft(d.pop())
旋转一步相当于,向左旋转一步相当于d.append(d.popleft())
。
Deque对象还提供一个只读属性:
maxlen
- 一个双端队列的最大大小或
None
无边界。3.1版中的新功能。
除上述外,双端支持迭代,酸洗,len(d)
, reversed(d)
,copy.copy(d)
,copy.deepcopy(d)
,会员与测试in
操作,并标引用,如d[-1]
。索引访问在两端都是O(1),但在中间减慢到O(n)。对于快速随机访问,请改用列表。
在3.5版本开始,双端的支持__add__()
,__mul__()
和__imul__()
。
例:
>>> from collections import deque
>>> d = deque('ghi') # make a new deque with three items
>>> for elem in d: # iterate over the deque's elements
... print(elem.upper())
G
H
I
>>> d.append('j') # add a new entry to the right side
>>> d.appendleft('f') # add a new entry to the left side
>>> d # show the representation of the deque
deque(['f', 'g', 'h', 'i', 'j'])
>>> d.pop() # return and remove the rightmost item
'j'
>>> d.popleft() # return and remove the leftmost item
'f'
>>> list(d) # list the contents of the deque
['g', 'h', 'i']
>>> d[0] # peek at leftmost item
'g'
>>> d[-1] # peek at rightmost item
'i'
>>> list(reversed(d)) # list the contents of a deque in reverse
['i', 'h', 'g']
>>> 'h' in d # search the deque
True
>>> d.extend('jkl') # add multiple elements at once
>>> d
deque(['g', 'h', 'i', 'j', 'k', 'l'])
>>> d.rotate(1) # right rotation
>>> d
deque(['l', 'g', 'h', 'i', 'j', 'k'])
>>> d.rotate(-1) # left rotation
>>> d
deque(['g', 'h', 'i', 'j', 'k', 'l'])
>>> deque(reversed(d)) # make a new deque in reverse order
deque(['l', 'k', 'j', 'i', 'h', 'g'])
>>> d.clear() # empty the deque
>>> d.pop() # cannot pop from an empty deque
Traceback (most recent call last):
File "<pyshell#6>", line 1, in -toplevel-
d.pop()
IndexError: pop from an empty deque
>>> d.extendleft('abc') # extendleft() reverses the input order
>>> d
deque(['c', 'b', 'a'])
deque
食谱
本节介绍了处理deques的各种方法。
有界长度deques提供类似于tail
Unix中的过滤器的功能:
def tail(filename, n=10):
'Return the last n lines of a file'
with open(filename) as f:
return deque(f, n)
使用deques的另一种方法是通过向右追加并弹出到左侧来维护一系列最近添加的元素:
def moving_average(iterable, n=3):
# moving_average([40, 30, 50, 46, 39, 44]) --> 40.0 42.0 45.0 43.0
# http://en.wikipedia.org/wiki/Moving_average
it = iter(iterable)
d = deque(itertools.islice(it, n-1))
d.appendleft(0)
s = sum(d)
for elem in it:
s += elem - d.popleft()
d.append(elem)
yield s / n
甲循环调度可以与存储在输入迭代来实现deque
。值从位置零处的活动迭代器产生。如果该迭代器耗尽,可以将其删除popleft()
; 否则,它可以通过以下方法循环回到最后rotate()
:
def roundrobin(*iterables):
"roundrobin('ABC', 'D', 'EF') --> A D E B F C"
iterators = deque(map(iter, iterables))
while iterators:
try:
while True:
yield next(iterators[0])
iterators.rotate(-1)
except StopIteration:
# Remove an exhausted iterator.
iterators.popleft()
该rotate()
方法提供了一种实现deque
切片和删除的方法。例如,纯Python实现依赖于定位要弹出的元素的方法:del d[n]
rotate()
def delete_nth(d, n):
d.rotate(-n)
d.popleft()
d.rotate(n)
要实现deque
切片,请使用类似的方法应用于 rotate()
将目标元素置于双端队列的左侧。删除旧条目popleft()
,添加新条目extend()
,然后反转旋转。随着对这种做法的微小变化,很容易实现第四风格栈操作,如dup
,drop
,swap
,over
,pick
, rot
,和roll
。