PyMOTW: collections

优质

小牛编辑

131浏览

2023-12-01

collections模块包含了一些除了内置类型, 如列表, 字典外的容器数据类型.

模块: collections
目的: 数据类型的包含容器.
Python 版本: 2.4 +

双端队列

一个双头队列, 或者”双端队列”, 支持从每一端上增加和删除元素. 更常用的像栈和队列, 它们可看成是双端队列的特殊情况, 即被限制为输入和输出只能从一端进行.

因为双端队列是一种序列容器, 所以它们支持一些列表也支持的相同操作, 如利用__getitem__()检查内部元素, 计算长度, 根据标识符的匹配与否来移除某个元素.

import collections

d = collections.deque('abcdefg')

print 'Deque:', d
print 'Length:', len(d)
print 'Left end:', d[0]
print 'Right end:', d[-1]


d.remove('c')

print 'remove(c):', d

$ python collections_deque.py
Deque: deque(['a', 'b', 'c', 'd', 'e', 'f', 'g'])
Length: 7
Left end: a
Right end: g
remove(c): deque(['a', 'b', 'd', 'e', 'f', 'g'])

一个双端队列可以从每一端填入元素, 在Python实现中使用词语 “left” 和 “right”.

import collections

# Add to the right ## 增加到右边, 使用extend和append
d = collections.deque()
d.extend('abcdefg')
print 'extend :', d
d.append('h')
print 'append :', d

# Add to the left ## 增加到左边, 使用extendleft和appendleft
d = collections.deque()
d.extendleft('abcdefg')
print 'extendleft:', d
d.appendleft('h')
print 'appendleft:', d

Note

extendleft()将对所有的输入进行, 其执行效果等价于对每一个元素进行appendleft(). 最终的结果是这个双端队列包含了一个逆序的输入元素序列.

$ python collections_deque_populating.py
extend : deque(['a', 'b', 'c', 'd', 'e', 'f', 'g'])
append : deque(['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'])
extendleft: deque(['g', 'f', 'e', 'd', 'c', 'b', 'a'])
appendleft: deque(['h', 'g', 'f', 'e', 'd', 'c', 'b', 'a'])

类似的, 双端队列可以同时从两端或只从一端获取元素, 具体得看你在算法中是如何写的.

import collections

print 'From the right:'
d = collections.deque('abcdefg')

while True:
    try:
        print d.pop() ## 从右
    except IndexError:
        break


print 'From the left:'
d = collections.deque('abcdefg')

while True:
    try:
        print d.popleft() ## 从左
    except IndexError:
        break

$ python collections_deque_consuming.py
From the right:
g
f
e
d
c
b
a
From the left:
a
b
c
d
e
f
g

因为双端队列是线程安全的, 所以你甚至可以在独立线程中从它的两端同时获取元素.

import collections
import threading
import time

candle = collections.deque(xrange(11))

def burn(direction, nextSource):
    while True:
        try:
            next = nextSource()
        except IndexError:
            break
        else:
            print '%8s: %s' % (direction, next)
            time.sleep(0.1)
    print '%8s done' % direction
    return


left = threading.Thread(target=burn, args=('Left', candle.popleft))
right = threading.Thread(target=burn, args=('Right', candle.pop))

left.start()
right.start()

left.join()
right.join()

$ python collections_deque_both_ends.py
Left: 0
Right: 10
Left: 1
Right: 9
Left: 2
Right: 8
Left: 3
Right: 7
Left: 4
Right: 6
Left: 5
Right done
Left done

另外一个双端队列有用的功能是在每一个方向上转动一些项, 以跳过某些项.

import collections

d = collections.deque(xrange(10))
print 'Normal :', d

d = collections.deque(xrange(10))
d.rotate(2) ## 向右旋转两个元素
print 'Right rotation:', d

d = collections.deque(xrange(10))
d.rotate(-2) ## 向左旋转两个元素
print 'Left rotation :', d

从右边旋转(使用一个正数)双端队列, 将项向右移动至右端末尾, 对于超过右边界的项又被移动到双端队列的左边. 从左边旋转(使用一个负数)双端队列, 将项向左边移至左端末尾, 对于超过左边界的项又被移动到双端队列的右边.

$ python collections_deque_rotate.py
Normal : deque([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])
Right rotation: deque([8, 9, 0, 1, 2, 3, 4, 5, 6, 7])
Left rotation : deque([2, 3, 4, 5, 6, 7, 8, 9, 0, 1])

defaultdict

标准的字典包含了setdefault(), 用于设置一个默认值, 即当查找一个不存在的键值时用这个默认值来代替. 同样的, defaultdict能够让你在初始化时指定默认值.

import collections

def default_factory():
    return 'default value'


d = collections.defaultdict(default_factory, foo='bar')
print d
print d['foo']
print d['bar']

$ python collections_defaultdict.py
defaultdict(<function default_factory at 0x7ca70>, {'foo': 'bar'})
bar
default value

这个例子中, 所有键都使用相同的默认值. 当默认的是一个用于集成或累计值的类型, 如一个列表, 集合, 甚至是整型时会更有用处. 标准库文档包含了许多使用defaultdict的例子.

##更多的defaultdict例子

defaultdict的第一个参数default_factory, 提供了初始值, 默认为None, 余下的参数被看作是字典的键值对.

例子1: 字典值默认是一个空列表

>>> s = [('yellow', 1), ('blue', 2), ('yellow', 3), ('blue', 4), ('red', 1)]
>>> d = defaultdict(list)
>>> for k, v in s:
 d[k].append(v)

>>> d.items()
[('blue', [2, 4]), ('red', [1]), ('yellow', [1, 3])]

例子2: 和上同样的效果, 只是使用了dict

>>> d = {}
>>> for k, v in s:
    d.setdefault(k, []).append(v)

>>> d.items()
[('blue', [2, 4]), ('red', [1]), ('yellow', [1, 3])]

例子3: 值默认为整型, 其整型值默认为0

>>> s = 'mississippi'
>>> d = defaultdict(int)
>>> for k in s:
 d[k] += 1

>>> d.items()
[('i', 4), ('p', 2), ('s', 4), ('m', 1)]

例子4:

>>> def constant_factory(value):
... return itertools.repeat(value).next
>>> d = defaultdict(constant_factory('<missing>'))
>>> d.update(name='John', action='ran')
>>> '%(name)s %(action)s to %(object)s' % d ## 字符串格式化中, 还可以利用字典的key
'John ran to <missing>'

例子5:

>>> s = [('red', 1), ('blue', 2), ('red', 3), ('blue', 4), ('red', 1), ('blue', 4)]
>>> d = defaultdict(set)
>>> for k, v in s:
 d[k].add(v)

>>> d.items()
[('blue', set([2, 4])), ('red', set([1, 3]))]

PyMOTW: collections

双端队列

defaultdict

参考