8.3. 集合-高性能容器数据类型

2.4 版的新Function。

源代码： Lib/collections.py和Lib/_abcoll.py

该模块实现了专门的容器数据类型，为 Python 的通用内置容器dict，list，set和tuple提供了替代方法。

namedtuple() 使用命名字段创建 Tuples 子类的工厂函数 2.6 版的新Function。
deque 列表式容器，两端都有快速追加和弹出 2.4 版的新Function。
Counter dict 子类，用于计算可哈希对象 2.7 版的新Function。
OrderedDict 记住命令条目已添加的 dict 子类 2.7 版的新Function。
defaultdict dict 子类，调用工厂函数以提供缺失值 2.5 版的新Function。

除了具体的容器类之外，collections 模块还提供抽象 Base Class，该抽象 Base Class可用于测试类是否提供了特定的接口，例如，它是否可哈希或 Map。

8.3.1. 柜台对象

提供了一种计数器工具来支持便捷而快速的计数。例如：

>>> # Tally occurrences of words in a list
>>> cnt = Counter()
>>> for word in ['red', 'blue', 'red', 'green', 'blue', 'blue']:
...     cnt[word] += 1
>>> cnt
Counter({'blue': 3, 'red': 2, 'green': 1})

>>> # Find the ten most common words in Hamlet
>>> import re
>>> words = re.findall(r'\w+', open('hamlet.txt').read().lower())
>>> Counter(words).most_common(10)
[('the', 1143), ('and', 966), ('to', 762), ('of', 669), ('i', 631),
 ('you', 554),  ('a', 546), ('my', 514), ('hamlet', 471), ('in', 451)]

元素是从* iterable 计数的，或者是从另一个 mapping *(或计数器)初始化的：

>>> 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

计数器对象具有一个字典接口，只是它们为缺失的项目返回零计数，而不是引发KeyError：

>>> c = Counter(['eggs', 'ham'])
>>> c['bacon']                              # count of a missing element is zero
0

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

>>> c['sausage'] = 0                        # counter entry with a zero count
>>> del c['sausage']                        # del actually removes the entry

2.7 版的新Function。

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

>>> c = Counter(a=4, b=2, c=0, d=-2)
>>> list(c.elements())
['a', 'a', 'a', 'a', 'b', 'b']

>>> Counter('abracadabra').most_common(3)
[('a', 5), ('r', 2), ('b', 2)]

>>> 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个对象，除了两个计数器的工作方式不同。

使用Counter对象的常见模式：

sum(c.values())                 # total of all counts
c.clear()                       # reset all counts
list(c)                         # list unique elements
set(c)                          # convert to a set
dict(c)                         # convert to a regular dictionary
c.items()                       # convert to a list of (elem, cnt) pairs
Counter(dict(list_of_pairs))    # convert from a list of (elem, cnt) pairs
c.most_common()[:-n-1:-1]       # n least common elements
c += Counter()                  # remove zero and negative counts

提供了几种 math 运算来组合Counter对象以产生多集(计数大于零的计数器)。加减法pass增加或减少相应元素的计数来组合计数器。交集和并集返回相应计数的最小值和最大值。每个操作都可以接受带符号计数的 Importing，但是输出将排除计数为零或更少的结果。

>>> c = Counter(a=3, b=1)
>>> d = Counter(a=1, b=2)
>>> c + d                       # add two counters together:  c[x] + d[x]
Counter({'a': 4, 'b': 3})
>>> c - d                       # subtract (keeping only positive counts)
Counter({'a': 2})
>>> c & d                       # intersection:  min(c[x], d[x])
Counter({'a': 1, 'b': 1})
>>> c | d                       # union:  max(c[x], d[x])
Counter({'a': 3, 'b': 2})

Note

计数器主要用于与正整数一起表示运行计数。但是，请注意不要不必要地排除需要其他类型或负值的用例。为了帮助解决这些用例，本节介绍了最小范围和类型限制。

  • Counter类本身是一个字典子类，对其键和值没有限制。这些值旨在为代表计数的数字，但是您可以*在值字段中存储任何内容。

  • most_common()方法仅要求值是可排序的。

  • 对于诸如c[key] += 1之类的就地操作，值类型仅需要支持加法和减法。因此，分数，浮点数和小数将起作用，并且支持负值。 update()和subtract()的情况也相同，它们允许 Importing 和输出均为负值和零值。

  • 多重集方法仅设计用于具有正值的用例。Importing 可以为负或零，但仅创建具有正值的输出。没有类型限制，但是值类型需要支持加，减和比较。

  • elements()方法需要整数计数。它忽略零和负计数。

See also

Note

map(Counter，groups_with_replacement('ABC'，2))–> AA AB AC BB BC CC

8.3.2. deque 对象

deque 是堆栈和队列的概括(名称发音为“ deck”，是“deque”的缩写)。deque 从 deque 的任一侧支持线程安全，内存高效的追加和弹出，并且在任一方向上的性能都大致相同。

尽管list对象支持类似的操作，但它们已针对快速固定长度的操作进行了优化，并且对pop(0)和insert(0, v)操作产生了 O(n)内存移动成本，这会改变基础数据表示的大小和位置。

2.4 版的新Function。

如果未指定* maxlen *或None，则 deque 可能增长到任意长度。否则，deque 限制为指定的最大长度。一旦限定长度的 deque 已满，则在添加新项目时，将从另一端丢弃相应数量的项目。有界长度 deque 提供的Function类似于 Unix 中的tail过滤器。它们对于跟踪事务和仅关注最近活动的其他数据池也很有用。

在 2.6 版中进行了更改：添加了* maxlen *参数。

deque 对象支持以下方法：

2.7 版的新Function。

2.5 版的新Function。

2.7 版的新Function。

当 deque 不为空时，向右旋转一个步骤等效于d.appendleft(d.pop())，向左旋转一个步骤等效于d.append(d.popleft())。

deque 对象还提供一个只读属性：

2.7 版的新Function。

除上述内容外，deque 支持迭代，Pickling，len(d)，reversed(d)，copy.copy(d)，copy.deepcopy(d)，使用in运算符进行成员资格测试以及下标引用(例如d[-1])。索引访问在两端均为 O(1)，但在中间则减慢为 O(n)。为了快速随机访问，请改用列表。

Example:

>>> 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'])

8.3.2.1. 双向队列

本节显示使用 deque 的各种方法。

有界长度 deque 提供的Function类似于 Unix 中的tail过滤器：

def tail(filename, n=10):
    'Return the last n lines of a file'
    return deque(open(filename), n)

使用 deque 的另一种方法是pass追加到右侧并弹出到左侧来维护一系列最近添加的元素：

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 / float(n)

rotate()方法提供了一种实现deque切片和删除的方法。例如，del d[n]的纯 Python 实现依靠rotate()方法来定位要弹出的元素：

def delete_nth(d, n):
    d.rotate(-n)
    d.popleft()
    d.rotate(n)

要实现deque切片，请使用类似的方法应用rotate()将目标元素移到 deque 的左侧。使用popleft()删除旧条目，使用extend()添加新条目，然后反转旋转。pass对该方法进行较小的更改，可以轻松实现 Forth 样式的堆栈操作，例如dup，drop，swap，over，pick，rot和roll。

8.3.3. defaultdict 对象

第一个参数提供default_factory属性的初始值；它默认为None。其余所有参数都与传递给dict构造函数一样，包括关键字参数。

2.5 版的新Function。

defaultdict对象除了标准dict操作之外还支持以下方法：

如果default_factory不是None，则在不带参数的情况下调用它以提供给定* key 的默认值，此值将插入 key *的字典中并返回。

如果调用default_factory引发异常，则此异常将不更改地传播。

当找不到请求的密钥时，此方法由dict类的getitem()方法调用；请参见getitem()返回或引发的任何东西都将返回或引发。

请注意，除getitem()之外，没有其他操作被调用missing()。这意味着get()像普通词典一样，将默认返回None而不是使用default_factory。

defaultdict个对象支持以下实例变量：

8.3.3.1. defaultdict 示例

使用list作为default_factory，可以很容易地将一组键值对组合成一个列表字典：

>>> 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])]

首次遇到每个键时，它尚未在 Map 中；因此，将使用default_factory函数自动创建一个条目，该函数返回一个空的list。 list.append()操作然后将值附加到新列表。当再次遇到键时，查找将正常进行(返回该键的列表)，并且list.append()操作将另一个值添加到列表中。此技术比使用dict.setdefault()的等效技术更简单，更快捷：

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

将default_factory设置为int可使defaultdict对计数很有用(例如手袋或其他语言的多件套商品)：

>>> s = 'mississippi'
>>> d = defaultdict(int)
>>> for k in s:
...     d[k] += 1
...
>>> d.items()
[('i', 4), ('p', 2), ('s', 4), ('m', 1)]

首次遇到字母时，Map 中会缺少它，因此default_factory函数调用int()以提供默认计数零。然后，递增操作将为每个字母构建计数。

始终返回零的函数int()只是常量函数的一种特殊情况。创建常量函数的一种更快，更灵活的方法是使用itertools.repeat()，它可以提供任何常量值(不只是零)：

>>> 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
'John ran to <missing>'

将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)
...
>>> d.items()
[('blue', set([2, 4])), ('red', set([1, 3]))]

8.3.4. namedtuple()具有命名字段的 Tuples 的工厂函数

命名 Tuples 将含义分配给 Tuples 中的每个位置，并允许使用更具可读性的自记录代码。它们可以在使用常规 Tuples 的任何地方使用，并且它们增加了按名称而不是位置索引访问字段的能力。

除下划线开头的名称外，任何有效的 Python 标识符均可用于字段名。有效标识符由字母，数字和下划线组成，但不能以数字或下划线开头，并且不能为keyword，例如* class ， for ， return ， global ， pass ， print ，或 raise *。

如果* rename *为 true，则无效的字段名称将自动替换为位置名称。例如，['abc', 'def', 'ghi', 'abc']转换为['abc', '_1', 'ghi', '_3']，从而消除了关键字def和重复的字段名abc。

如果* verbose *为 true，则在构建类定义之前就将其打印出来。

命名 Tuples 实例没有按实例的字典，因此它们是轻量级的，并且不需要比常规 Tuples 更多的内存。

2.6 版的新Function。

在 2.7 版中进行了更改：添加了对* rename *的支持。

Example:

>>> Point = namedtuple('Point', ['x', 'y'], verbose=True)
class Point(tuple):
    'Point(x, y)'

    __slots__ = ()

    _fields = ('x', 'y')

    def __new__(_cls, x, y):
        'Create new instance of Point(x, y)'
        return _tuple.__new__(_cls, (x, y))

    @classmethod
    def _make(cls, iterable, new=tuple.__new__, len=len):
        'Make a new Point object from a sequence or iterable'
        result = new(cls, iterable)
        if len(result) != 2:
            raise TypeError('Expected 2 arguments, got %d' % len(result))
        return result

    def __repr__(self):
        'Return a nicely formatted representation string'
        return 'Point(x=%r, y=%r)' % self

    def _asdict(self):
        'Return a new OrderedDict which maps field names to their values'
        return OrderedDict(zip(self._fields, self))

    def _replace(_self, **kwds):
        'Return a new Point object replacing specified fields with new values'
        result = _self._make(map(kwds.pop, ('x', 'y'), _self))
        if kwds:
            raise ValueError('Got unexpected field names: %r' % kwds.keys())
        return result

    def __getnewargs__(self):
        'Return self as a plain tuple.  Used by copy and pickle.'
        return tuple(self)

    __dict__ = _property(_asdict)

    def __getstate__(self):
        'Exclude the OrderedDict from pickling'
        pass

    x = _property(_itemgetter(0), doc='Alias for field number 0')

    y = _property(_itemgetter(1), doc='Alias for field number 1')

>>> p = Point(11, y=22)     # instantiate with positional or keyword arguments
>>> p[0] + p[1]             # indexable like the plain tuple (11, 22)
33
>>> x, y = p                # unpack like a regular tuple
>>> x, y
(11, 22)
>>> p.x + p.y               # fields also accessible by name
33
>>> p                       # readable __repr__ with a name=value style
Point(x=11, y=22)

命名 Tuples 对于将字段名称分配给csv或sqlite3模块返回的结果 Tuples 特别有用：

EmployeeRecord = namedtuple('EmployeeRecord', 'name, age, title, department, paygrade')

import csv
for emp in map(EmployeeRecord._make, csv.reader(open("employees.csv", "rb"))):
    print emp.name, emp.title

import sqlite3
conn = sqlite3.connect('/companydata')
cursor = conn.cursor()
cursor.execute('SELECT name, age, title, department, paygrade FROM employees')
for emp in map(EmployeeRecord._make, cursor.fetchall()):
    print emp.name, emp.title

除了从 Tuples 继承的方法外，命名 Tuples 还支持三种其他方法和一种属性。为避免与字段名称冲突，方法和属性名称以下划线开头。

>>> t = [11, 22]
>>> Point._make(t)
Point(x=11, y=22)

>>> p = Point(x=11, y=22)
>>> p._asdict()
OrderedDict([('x', 11), ('y', 22)])

在 2.7 版中更改：返回OrderedDict而不是常规dict。

>>> p = Point(x=11, y=22)
>>> p._replace(x=33)
Point(x=33, y=22)

>>> for partnum, record in inventory.items():
...     inventory[partnum] = record._replace(price=newprices[partnum], timestamp=time.now())

>>> p._fields            # view the field names
('x', 'y')

>>> Color = namedtuple('Color', 'red green blue')
>>> Pixel = namedtuple('Pixel', Point._fields + Color._fields)
>>> Pixel(11, 22, 128, 255, 0)
Pixel(x=11, y=22, red=128, green=255, blue=0)

要检索名称存储在字符串中的字段，请使用getattr()函数：

>>> getattr(p, 'x')
11

要将字典转换为命名的 Tuples，请使用 double-star-operator(如解包参数列表中所述)：

>>> d = {'x': 11, 'y': 22}
>>> Point(**d)
Point(x=11, y=22)

由于命名的 Tuples 是常规的 Python 类，因此使用子类轻松添加或更改Function。这是添加计算字段和固定宽度打印格式的方法：

>>> class Point(namedtuple('Point', 'x y')):
...     __slots__ = ()
...     @property
...     def hypot(self):
...         return (self.x ** 2 + self.y ** 2) ** 0.5
...     def __str__(self):
...         return 'Point: x=%6.3f  y=%6.3f  hypot=%6.3f' % (self.x, self.y, self.hypot)
...
>>> for p in Point(3, 4), Point(14, 5/7.):
...     print p
Point: x= 3.000  y= 4.000  hypot= 5.000
Point: x=14.000  y= 0.714  hypot=14.018

上面显示的子类将__slots__设置为空 Tuples。pass防止创建实例字典，这有助于将内存需求保持在较低水平。

子类化对于添加新的存储字段没有用。相反，只需从_fields属性创建一个新的命名 Tuples 类型：

>>> Point3D = namedtuple('Point3D', Point._fields + ('z',))

可以pass使用_replace()来定制原型实例来实现默认值：

>>> Account = namedtuple('Account', 'owner balance transaction_count')
>>> default_account = Account('<owner name>', 0.0, 0)
>>> johns_account = default_account._replace(owner='John')

枚举常量可以用命名 Tuples 实现，但是使用简单的类语句更简单，更有效：

>>> Status = namedtuple('Status', 'open pending closed')._make(range(3))
>>> Status.open, Status.pending, Status.closed
(0, 1, 2)
>>> class Status:
...     open, pending, closed = range(3)

See also

命名 Tuples 食谱适用于 Python 2.4.

8.3.5. OrderedDict 对象

Sequences 词典与常规词典一样，但是它们记住项目插入的 Sequences。在有序字典上进行迭代时，将按其键首次添加的 Sequences 返回项目。

2.7 版的新Function。

除了常用的 Map 方法外，有序词典还支持使用reversed()进行反向迭代。

OrderedDict个对象之间的相等性测试对 Sequences 敏感，并被实现为list(od1.items())==list(od2.items())。像常规字典一样，OrderedDict对象与其他Mapping对象之间的相等性测试对 Sequences 不敏感。这样就可以在使用常规词典的任何地方替换OrderedDict个对象。

OrderedDict构造函数和update()方法都接受关键字参数，但是它们的 Sequences 丢失了，因为 Python 的函数调用语义使用常规无序字典传递关键字参数。

See also

在 Python 2.4 或更高版本上运行的等效 OrderedDict 配方。

8.3.5.1. OrderedDict 示例和食谱

由于有序字典会记住其插入 Sequences，因此可以将其与排序结合使用以创建排序后的字典：

>>> # regular unsorted dictionary
>>> d = {'banana': 3, 'apple': 4, 'pear': 1, 'orange': 2}

>>> # dictionary sorted by key
>>> OrderedDict(sorted(d.items(), key=lambda t: t[0]))
OrderedDict([('apple', 4), ('banana', 3), ('orange', 2), ('pear', 1)])

>>> # dictionary sorted by value
>>> OrderedDict(sorted(d.items(), key=lambda t: t[1]))
OrderedDict([('pear', 1), ('orange', 2), ('banana', 3), ('apple', 4)])

>>> # dictionary sorted by length of the key string
>>> OrderedDict(sorted(d.items(), key=lambda t: len(t[0])))
OrderedDict([('pear', 1), ('apple', 4), ('orange', 2), ('banana', 3)])

删除条目时，新排序的词典将保持其排序 Sequences。但是，当添加新键时，键会附加到末尾，并且不会保留排序。

创建一个有序的字典变体也很简单，该变体可以记住按键的* last *插入 Sequences。如果新条目覆盖现有条目，则原始插入位置将更改并移至末尾：

class LastUpdatedOrderedDict(OrderedDict):
    'Store items in the order the keys were last added'

    def __setitem__(self, key, value):
        if key in self:
            del self[key]
        OrderedDict.__setitem__(self, key, value)

可以将有序词典与Counter类结合使用，以便计数器记住第一次遇到的有序元素：

class OrderedCounter(Counter, OrderedDict):
     'Counter that remembers the order elements are first encountered'

     def __repr__(self):
         return '%s(%r)' % (self.__class__.__name__, OrderedDict(self))

     def __reduce__(self):
         return self.__class__, (OrderedDict(self),)

8.3.6. 集合抽象 Base Class

收款模块提供以下ABCs：

ABC Inherits from Abstract Methods Mixin Methods
Container __contains__
Hashable __hash__
Iterable __iter__
Iterator Iterable next __iter__
Sized __len__
Callable __call__
Sequence Sized, Iterable, Container __getitem__ , __len__ __contains__，__iter__，__reversed__，index和count
MutableSequence Sequence __getitem__ , __setitem__ , __delitem__ , __len__ , insert 继承了Sequence个方法以及append，reverse，extend，pop，remove和__iadd__
Set Sized, Iterable, Container __contains__ , __iter__ , __len__ __le__，__lt__，__eq__，__ne__，__gt__，__ge__，__and__，__or__，__sub__，__xor__和isdisjoint
MutableSet Set __contains__ , __iter__ , __len__ , add , discard 继承了Set个方法以及clear，pop，remove，__ior__，__iand__，__ixor__和__isub__
Mapping Sized, Iterable, Container __getitem__ , __iter__ , __len__ __contains__，keys，items，values，get，__eq__和__ne__
MutableMapping Mapping __getitem__ , __setitem__ , __delitem__ , __iter__ , __len__ 继承了Mapping个方法以及pop，popitem，clear，update和setdefault
MappingView Sized __len__
ItemsView MappingView, Set __contains__ , __iter__
KeysView MappingView, Set __contains__ , __iter__
ValuesView MappingView __contains__ , __iter__

这些 ABC 允许我们询问类或实例是否提供特定Function，例如：

size = None
if isinstance(myvar, collections.Sized):
    size = len(myvar)

几种 ABC 可用作混合器，使开发支持容器 API 的类更加容易。例如，要编写一个支持完整的Set API 的类，只需提供三个底层抽象方法：contains()，iter()和len()。 ABC 提供其余方法，例如and()和isdisjoint()

class ListBasedSet(collections.Set):
     ''' Alternate set implementation favoring space over speed
         and not requiring the set elements to be hashable. '''
     def __init__(self, iterable):
         self.elements = lst = []
         for value in iterable:
             if value not in lst:
                 lst.append(value)

     def __iter__(self):
         return iter(self.elements)

     def __contains__(self, value):
         return value in self.elements

     def __len__(self):
         return len(self.elements)

s1 = ListBasedSet('abcdef')
s2 = ListBasedSet('defghi')
overlap = s1 & s2            # The __and__() method is supported automatically

有关将Set和MutableSet用作混合的注意事项：

See also

首页