Python中的Collections模块

Collections是 Python 的内置集合模块，提供了很多方便且高性能的特殊容器数据类型，即除了 Python 通用内置容器： dict、list、set 和 tuple 等的替代方案，掌握这些知识有助于提高代码的性能和可读性。在 IDLE 输入 help(collections) 可查看帮助文档，其中常见的类/函数如下：

namedtuple

Python 内建普通元组 tuple 存在一个局限，即不能为 tuple 中的元素命名，故 tuple 所要表达的意义并不明显。因此，引入一工厂函数（factory function）collections.namedtuple，以构造一个带字段名的 tuple。具名元组 namedtuple 的实例和普通元组 tuple消耗的内存一样多（因为字段名都被保存在对应的类中）但却更具可读性（namedtuple 使 tuple 变成自文档，根据字段名很容易理解用途），令代码更易维护；同时，namedtuple 不用命名空间字典（namespace dictionary）__dict__来存放/维护实例属性，故比普通 dict 更加轻量和快速。但注意，具名元组 namedtuple 继承自 tuple ，其中的属性均不可变。

其用法如下：

collections.namedtuple(typename, field_names, *, verbose=False, rename=False, module=None)

namedtuple，顾名思义是已具命名的元组（简称具名元组），它返回一个 tuple 子类。

其中，

• namedtuple名称为参数typename，各字段名称为参数field_names。

• field_names既可以是一个类似 [‘x’, ‘y’] 的字符串序列（string-seq），也可以是用空格或逗号分隔开的纯字符串 string，如 ‘x y’ 或 ‘x, y’。任何 Python 的有效标识符都可作为字段名。所谓有效标识符由字母，数字，下划线组成，但首字母不能是数字或下划线，且不能与 Python 关键词重复，如class, for, return等。

具名元组 namedtuple 向后兼容普通 tuple，从而既可通过 field_names获取元素值/字段值，也能通过索引和迭代获取元素值/字段值。

来一点例子说明以下用法~

首先来看看如何初始化，下面这三种方式等价。

>>> from collections import namedtuple
>>> Point = namedtuple("Point", 'x, y')
>>> Point = namedtuple("Point", 'x y')
>>> Point = namedtuple("Point", ['x', 'y'])

实例化具名数组：

>>> p = Point(2, 3)
>>> p
Point(x=2, y=3)

通过字段名获取元素值/字段值

>>> p.x
2

通过索引获取元素值/字段值

>>> p[0]
2

通过迭代获取元素值/字段值

>>> for i in p:
...     print(i)
...
2
3

能够像普通 tuple 一样解绑

>>> a, b = p
>>> a, b
(2, 3)

除继承普通 tuple，具名元组 nametuple 还额外支持三个方法和两个属性。为防止名称冲突，方法和属性以下划线开始：

• 类属性_fields：包含本类所有字段名的元组 tuple

• 类方法_make(iterable)：接受一个序列 sequence 或可迭代对象 iterable 来生成本类的实例

• 实例方法_replace(**kwargs)：基于本实例修改、替换元素来生成本类的实例

• 实例方法_asdict()：将具名元组以 collections.OrdereDict 的形式返回，用于友好地展示元组信息

• 实例方法_source：…

来看例子：

1. 初始化一个具名元组对象 Point

>>> from collections import namedtuple
>>> Point = namedtuple("Point", ['x', 'y'])
>>> p = Point(10, 40)

2. _fields

>>> p._fields  # 获取所有字段名构成的 tuple
('x', 'y')

3. _make

>>> p2 = p._make([5, 6])   # 使用 list 实例化一个新 Point2 对象
>>> p2
Point(x=5, y=6)
>>> p
Point(x=10, y=40)   # 原 namedtuple 不变

4. _asdict

>>> p2._asdict()  # 将 namedtuple 对象转换为 OrderedDict 对象
OrderedDict([('x', 5), ('y', 6)])
>>> p2
Point(x=5, y=6)   # 原 namedtuple 不变

注意，上述方法均非“原地操作” (in-place) 方法，因为 tuple / namedtuple 是不可变对象，只能创建新的。

若参数rename=True，无效字段名field_names自动转换成位置名。例如 ['abc','def','ghi','abc'] 转换成['abc','_1','ghi','_3']，转换并消除了关键词def和重复域名abc。否则，在创建伊始就会抛出ValueError。

>>> Point3 = namedtuple("Point3", ['abc', 'def', 'ghi', 'abc'], rename=True)
>>> p3 = Point3(3, 5, 7, 9)
>>> p3._fields
('abc', '_1', 'ghi', '_3')
>>> p3
Point3(abc=3, _1=5, ghi=7, _3=9)

此外，将 dict 转换为namedtuple可使用双星操作符 (double-star-operator) 进行解包实现：

>>> dict4 = {'x':1, 'y':2}
>>> Point4 = namedtuple("Point4", 'x y')
>>> p4 = Point4(**dict4)
>>> p4
Point4(x=1, y=2)

事实上，这个方法我用的最多的就是在强化学习中，存储经验池的时候了。（deque下面讲~）

from collections import namedtuple, deque

replay_buffer = deque(maxlen=10000)
Transition = namedtuple('Transition', ('state', 'action', 'reward', 'next_state', 'done'))
transition = Transition(s, a, r, s_, done)
replay_buffer.append(transition)

ChainMap

ChainMap类提供一个快速链接多个映射（字典）的操作。通常情况下，他会比创建字典然后调用update()快。该类可用于模拟嵌套作用域，在模板中很有用。

实现：

class collections.ChainMap(*maps)

ChainMap类组合多个字典或其他映射到一个可更新的、单一的对象中。如果没有指定maps，就会提供一个空字典，以此来保证每个新链中都会有至少一个字典（映射）。

底层映射存储在列表中。 该列表是公共的，可以使用maps属性访问或更新。

>>> from collections import ChainMap
>>> m1 = {'color': 'red', 'user': 'guest'}
>>> m2 = {'name': 'drfish', 'age': '18'}
>>> chain_map = ChainMap(m1, m2)
>>> chain_map
ChainMap({'color': 'red', 'user': 'guest'}, {'name': 'drfish', 'age': '18'})
>>> chain_map.get('name')
'drfish'
>>> chain_map.get('user')
'guest'

ChainMap除了支持所有常用的字典方法以外，还支持以下属性：

1. maps返回一个用户可以更新的映射列表。他是按照搜索顺序排序的。

>>> chain_map.maps
[{'color': 'red', 'user': 'guest'}, {'name': 'drfish', 'age': '18'}]

2. new_child(m=None)：返回一个新的ChainMap，这个新ChainMap包含新添加的map，并且这个map在首位。如果没有指定m，那么就会在最前面添加一个空dict。因此d.new_child()相当于ChainMap({}, *d.maps)。

>>> m3 = {'data': '1-6'}
>>> chain_map.new_child(m=m3)
ChainMap({'data': '1-6'}, {'color': 'red', 'user': 'guest'}, {'name': 'drfish', 'age': '18'})
>>> chain_map
ChainMap({'color': 'red', 'user': 'guest'}, {'name': 'drfish', 'age': '18'})
>>> id(chain_map.new_child(m=m3))
2030211519560
>>> id(chain_map)
2030211705480

需要注意的是，这将产生一个全新的ChainMap，和之前的互不干扰

3. parents：返回一个新的ChainMap，这个新ChainMap不包括第一个dict。这个对于跳过第一个map搜索很有用。d.parents大致相当于ChainMap(*d.maps[1:])。

>>> chain_map.parents
ChainMap({'name': 'drfish', 'age': '18'})
>>> chain_map
ChainMap({'color': 'red', 'user': 'guest'}, {'name': 'drfish', 'age': '18'})
>>> id(chain_map.parents)
2030211416712
>>> id(chain_map)
2030211705480

deque

deque 是一个双端队列。普通队列只能在队尾添加，队头弹出。而双端队列在队尾和队头都可以添加和弹出。队尾的添加和弹出可以看成栈，队尾的添加和队头的弹出可以看成队列。

deque是一种类似于栈和队列的容器，它有如下优点：

1. deque支持线程安全；

2. 在deque两端做append和pop操作的时间复杂度都为O ( 1 ) O(1)O(1)；

3. 相对于列表来说deque能做更多的事，而且效率更高；

4. 在创建deque时我们可以通过参数maxlen来指定它长度，在deque长度达到饱和时，如果继续向里面添加元素，那么相应的多余的元素会从添加元素相反的方向给删除掉。

deque支持如下的方法来操作deque里面的元素：

• append(x)：在deque的右端添加元素x。

• appendleft(x)：在deque的左端添加元素x。

• clear()：清空deque里面的所有元素。

• copy()：创建一份deque的浅拷贝。

• count(x)：在deque中统计元素x出现的次数。

• extend(iterable)：在deque的右端将iterable里面的所有元素依次添加进来。

• extendleft(iterable)：在deque的左端将iterable里面的所有元素依次添加进来。

• index(x[, start[, stop]])：在deque的指定索引范围内查找元素x并返回第一个x的索引，没有则会抛出ValueError的异常。

• insert(i, x)：将元素x插入到deque中位置为i的地方。如果在插入元素后deque超出了最大长度则会抛出IndexError的异常。

• pop()：删除并返回deque中最右端的元素。如果deque为空则会抛出IndexError的异常。

• popleft()：删除并返回deque中最左端的元素。如果deque为空则会抛出IndexError的异常。

• remove(value)：删除在deque中找到的第一个元素value，如果没有找到则会抛出ValueError的异常。

• reverse()：原地翻转deque，返回值为None。

• rotate(n=1)：将deque右边n个元素进行旋转，如果n为负数，则将deque左边的n个元素进行旋转。

下面举一些例子：

1. deque支持索引。比如d[0]：访问并返回队头元素，但不弹出，如果双端队列为空会报错。

>>> from collections import deque
>>> d = deque()
>>> d.append(1)
>>> d.appendleft(2)
>>> d.append(3)
>>> d.appendleft(4)
>>> d.append(50)
>>> d
deque([4, 2, 1, 3, 50])
>>> d[0]
4
>>> d[-1]
50

2. rotate参数的用法：（rotate参数会更改原始deque）

>>> a = deque([1, 2, 3, 4, 5])
>>> a.rotate(3)
>>> a
deque([3, 4, 5, 1, 2])
>>> a.rotate(-3)
>>> a
deque([4, 5, 1, 2, 3])

3. extendleft参数用法：

>>> c = deque([2, 3, 4, 1, 9, 8])
>>> c.extendleft([1, 2, 3, 4, 5, 6])
>>> c
deque([6, 5, 4, 3, 2, 1, 2, 3, 4, 1, 9, 8])

4. 由于deque的结构带来的功能，可以把deque数据结构很简单的用作栈和队列。

1. deque用作栈 【先进后出】

>>> stack = deque()
>>> stack.append(1)  # 入栈
>>> stack.append(2)  # 入栈
>>> stack.append(3)  # 入栈
>>> stack.pop()  # 出栈
3
>>> stack.pop()  # 出栈
2
>>> stack.pop()  # 出栈
1
>>> stack
deque([])

5. deque用作队列 【先进先出】

>>> queue = deque()
>>> queue.append(1)  # 入队
>>> queue.append(2)  # 入队
>>> queue.append(3)  # 入队
>>> queue.popleft()  # 出队
1
>>> queue.popleft()  # 出队
2
>>> queue.popleft()  # 出队
3
>>> queue
deque([])

Counter

计数器是用于计数可哈希对象的dict子类。它是一个集合，其中元素存储为字典键，其计数存储为字典值。计数可以是任何整数值，包括零或负计数。

为了更清晰的感受这个函数有啥用，我们先来看一个简单的需求：统计词频。

1. 常规方法：

>>> colors = ['red', 'blue', 'red', 'green', 'blue', 'blue']
>>> result = {}
>>> for color in colors:
...     if result.get(color) == None:
...         result[color] = 1
...     else:
...         result[color] += 1
...
>>> result
{'red': 2, 'blue': 3, 'green': 1}

2. 利用Counter的简单实现

>>> from collections import Counter
>>> colors = ['red', 'blue', 'red', 'green', 'blue', 'blue']
>>> c = Counter(colors)
>>> dict(c)
{'red': 2, 'blue': 3, 'green': 1}

下面来看看Counter的具体用法。事实上，Counter中的元素是从一个可迭代的对象计数或从另一个映射（或计数器）初始化的。

>>> from collections import Counter
>>> c = Counter()                           # a new, empty counter
>>> c = Counter('gallahad')                 # a new counter from an iterable
>>> c = Counter({'red': 4, 'blue': 2})      # a new counter from a mapping
>>> c = Counter(cats=4, dogs=8)             # a new counter from keyword args

Counter对象具有一个字典接口，当访问不存在的值时，它为缺失项返回0计数，而字典会引发KeyError（因为访问了字典中不存在的键）：

>>> c = Counter(['eggs', 'ham'])
>>> c
Counter({'eggs': 1, 'ham': 1})
>>> c['bacon']
0

将计数设置为零不会将元素从计数器中删除。使用del将其完全删除：

>>> c['sausage'] = 0   # counter entry with a zero count
>>> c
Counter({'eggs': 1, 'ham': 1, 'sausage': 0})
>>> del c['sausage']   # del actually removes the entry
>>> c
Counter({'eggs': 1, 'ham': 1})

作为dict的子类，Counter继承了记住插入顺序的功能。对Counter对象的数学运算也保留顺序。根据在左操作数中首先遇到元素的时间，然后按照在右操作数中遇到的顺序，对结果进行排序。

常用的词典方法可用于Counter对象，但有两种方法对Counter的工作方式不同。

• fromkeys(iterable)：没有为Counter对象实现此类方法。

• update([iterable-or-mapping])：元素是从可迭代的或从另一个映射（或计数器）添加的元素中计数的。像dict.update()一样，但是添加计数而不是替换它们。同样，可迭代对象应该是元素序列，而不是(key,value)对序列。（在某种层面上，可以理解为加法运算）

除了适用于所有词典的方法外，Counter对象还支持三种方法：

1. elements()：在元素上返回一个迭代器，并重复与其计数相等的次数。元素按首先遇到的顺序返回。如果一个元素的数量少于一个，elements()将忽略它。

>>> a = Counter(a=4, b=3, c=10)
>>> a.elements()
<itertools.chain object at 0x000001D8B20BC048>
>>> sorted(a.elements())
['a', 'a', 'a', 'a', 'b', 'b', 'b', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c']

2. most_common([n])：返回n个最常见元素的列表及其从最常见到最小的计数。如果省略n或None，则most_common()返回计数器中的所有元素。具有相等计数的元素按首先遇到的顺序排序。查看最常见出现的k个元素：

>>> Counter('hfvisohvoisadiddjjfjfjfjjff').most_common(3)
[('f', 6), ('j', 6), ('i', 3)]

3. subtract([iterable-or-mapping])：从可迭代对象或另一个映射（或计数器）中减去元素。像dict.update()一样，但是减去计数而不是替换它们。输入和输出都可以为零或负。

>>> c = Counter(a=4, b=2, c=0, d=-2)
>>> d = Counter(a=1, b=2, c=3, d=4)
>>> c.subtract(d)
>>> c
Counter({'a': 3, 'b': 0, 'c': -3, 'd': -6})

Counter算术运算

>>> c = Counter(a=3, b=1)
>>> d = Counter(a=1, b=2)
>>> c + d
Counter({'a': 4, 'b': 3})
>>> c - d   # 相减，如果小于等于0，删去
Counter({'a': 2})
>>> c & d  # 求最小
Counter({'a': 1, 'b': 1})
>>> c | d  # 求最大
Counter({'a': 3, 'b': 2})

注意：这四个算术运算结果只含有计数为正的项，否则就是一个空 Counter()对象。 subtract()和 update()方法则没有这些特质。

实际例子：大文件统计词频并按照出现次数排序（文件是以空格隔开的单词的诸多句子）

from collections import Counter
result = Counter()
with open("input.txt","r") as f:
    while True:
        lines = f.read(1024).splitlines()
        if lines==[]:
            break
        lines = [lines[i].split(" ") for i in range(len(lines))]
        words = []
        for line in lines:
            words.extend(line)
        tmp = Counter(words)
        result += tmp   # Counter相加

print(result.most_common(10))

OrderedDict

Python中默认的字典dict是无序的，因为它是按照hash来存储的，但是collections模块中的OrderedDict子类实现了对字典对象中元素的排序，它是有序的。OrderedDict的key会按照插入的顺序排列，不是key本身排序。

OrderedDict的用法很简单，和dict是差不多的。例子如下：

>>> cache = collections.OrderedDict()
>>> cache["key1"] = {"k1": "v1"}
>>> cache["key3"] = {"k3": "v3"}
>>> cache["key2"] = {"k2": "v2"}
>>> cache
OrderedDict([('key1', {'k1': 'v1'}), ('key3', {'k3': 'v3'}), ('key2', {'k2': 'v2'})])
>>>
>>> cache["key4"] = {"k4": "v4"}
>>> cache
OrderedDict([('key1', {'k1': 'v1'}), ('key3', {'k3': 'v3'}), ('key2', {'k2': 'v2'}), ('key4', {'k4': 'v4'})])

OrderedDict.popitem()函数可以完成元素的删除操作，有一个可选参数last（默认为True），当last为True时它从OrderedDict中删除最后一个键值对并返回该键值对，当last为False时它从OrderedDict中删除第一个键值对并返回该键值对。

>>> cache = collections.OrderedDict()
>>> cache["key1"] = {"k1": "v1"}
>>> cache["key2"] = {"k2": "v2"}
>>> cache["key3"] = {"k3": "v3"}
>>> cache
OrderedDict([('key1', {'k1': 'v1'}), ('key2', {'k2': 'v2'}), ('key3', {'k3': 'v3'})])

>>> cache.popitem(last=False)
('key1', {'k1': 'v1'})
>>> cache
OrderedDict([('key2', {'k2': 'v2'}), ('key3', {'k3': 'v3'})])

>>> cache.popitem(last=True)
('key3', {'k3': 'v3'})
>>> cache
OrderedDict([('key2', {'k2': 'v2'})])

注意：如果字典已经为空，却调用了此方法，就报出KeyError异常，所以在写代码时需要捕获异常及做相应的处理。

字典里面还有另一种常用的删除方法pop()，pop(key[,default])，其中，key是必选参数，必须给出，default是可选参数，可以不给出。如果键值key在字典中存在，删除dict[key]，返回 dict[key]的value值。否则，如有给出default值则返回default值，如果default值没有给出，就会报出KeyError异常。pop()方法至少接受一个参数，最多接受两个参数。

>>> cache = collections.OrderedDict()
>>> cache["b"] = 2
>>> cache["c"] = 3
>>> cache["d"] = 4
>>> cache
OrderedDict([('a', 1), ('b', 2), ('c', 3), ('d', 4)])

>>> cache.pop("a")  # 删除存在的key：a
1
>>> cache
OrderedDict([('b', 2), ('c', 3), ('d', 4)])

>>> cache.pop("e")  # 删除不存在的key：e
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
KeyError: 'e'

>>> cache.pop("e", "Not Find")  # 设置default值的方法来避免报错
'Not Find'

defaultdict

Python中通过Key访问字典，当Key不存在时，会引发‘KeyError’异常。为了避免这种情况的发生，可以使用collections类中的defaultdict()方法来为字典提供默认值。

defaultdict是内置数据类型dict的一个子类，基本功能与dict一样，只是重写了一个方法missing(key)和增加了一个可写的对象变量default_factory。

语法格式

collections.defaultdict([default_factory[, …]])

missing(key)

• 如果default_factory属性为None，就报出以key作为遍历的KeyError异常；

• 如果default_factory不为None，就会向给定的key提供一个默认值，这个值插入到词典中，并返回；

• 如果调用default_factory报出异常，这个异常在传播时不会改变；

• 这个方法是当要求的key不存在时，dict类中的getitem()方法所调用，无论它返回或者报出什么，最终返回或报出给getitem()；

• 只有getitem()才能调用missing()，这意味着，如果get()起作用，如普通的词典，将会返回None作为默认值，而不是使用default_factory；

default_factory， 这个属性用于 missing()方法，使用构造器中的第一个参数初始化；
使用 list作为 default_factory，很容易将一个 key-value的序列转换为 list字典。

列表字典

>>> from collections import defaultdict
>>>
>>> s = [('yellow', 1), ('blue', 2), ('yellow', 3), ('blue', 4), ('red', 1)]
>>> d = defaultdict(list)
>>> for k, v in s:
...     d[k].append(v)
...
>>> a = d.items()
>>> print(a)
dict_items([('yellow', [1, 3]), ('blue', [2, 4]), ('red', [1])])

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

当字典中没有的键第一次出现时，default_factory自动为其返回一个空列表，list.append()会将值添加进新列表；再次遇到相同的键时，list.append()将其它值再添加进该列表。

这种方法比使用dict.setdefault()更为便捷，dict.setdefault()也可以实现相同的功能。

>>> e = {}
>>> for k, v in s:
...     e.setdefault(k, []).append(v)
...
>>> a = e.items()
>>> print(a)
dict_items([('yellow', [1, 3]), ('blue', [2, 4]), ('red', [1])])

>>> b = sorted(e.items())
>>> print(b)
[('blue', [2, 4]), ('red', [1]), ('yellow', [1, 3])]

下面来举几个常用的例子：

1. 计数：设置default_factory为int，使得defaultdict可以用于计数。

>>> s = "chlzdjlongdong"
>>> d = defaultdict(int)
>>> for k in s:
...     d[k] += 1
...
>>> a = d.items()
>>> print(a)
dict_items([('c', 1), ('h', 1), ('l', 2), ('z', 1), ('d', 2), ('j', 1), ('o', 2), ('n', 2), ('g', 2)])

>>> b = sorted(d.items())
>>> print(b)
[('c', 1), ('d', 2), ('g', 2), ('h', 1), ('j', 1), ('l', 2), ('n', 2), ('o', 2), ('z', 1)]

字符串中的字母第一次出现时，字典中没有该字母，default_factory函数调用int()为其提供一个默认值0，加法操作将计算出每个字母出现的次数。

>>> s = "chlzdjlongdong"
>>> d = defaultdict(int)
>>> for k in s:
...     d[k] += 1
...
>>> a = d.items()
>>> print(a)
dict_items([('c', 1), ('h', 1), ('l', 2), ('z', 1), ('d', 2), ('j', 1), ('o', 2), ('n', 2), ('g', 2)])

>>> b = sorted(d.items())
>>> print(b)
[('c', 1), ('d', 2), ('g', 2), ('h', 1), ('j', 1), ('l', 2), ('n', 2), ('o', 2), ('z', 1)]

2. 集合字典：将default_factory设置为set，使得defaultdict可以建立一个集合字典。

>>> 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)
...
>>> a = d.items()
>>> print(a)
dict_items([('red', {1, 3}), ('blue', {2, 4})])

>>> b = sorted(d.items())
>>> print(b)
[('blue', {2, 4}), ('red', {1, 3})]