Python 集合和多重集合

Python 集合和多重集合，本节将用标准库中的内置数据类型和类在Python中实现可变集合、不可变集合和多重集合（背包）数据结构。首先来快速回顾一下集合数据结构。

集合含有一组不含重复元素的无序对象。集合可用来快速检查元素的包含性，插入或删除值，计算两个集合的并集或交集。

在“合理”的集合实现中，成员检查预计耗时为。并集、交集、差集和子集操作应平均耗时为。Python标准库中的集合实现都具有这些性能指标。

与字典一样，集合在Python中也得到了特殊对待，有语法糖能够方便地创建集合。例如，花括号集合表达式语法和集合解析式能够方便地定义新的集合实例：

vowels = {'a', 'e', 'i', 'o', 'u'}
squares = {x * x for x in range(10)}

但要小心，创建空集时需要调用set()构造函数。空花括号{}有歧义，会创建一个空字典。

Python及其标准库提供了几个集合实现，让我们看看。

Python 集合和多重集合 set——首选集合实现

set是Python中的内置集合实现。set类型是可变的，能够动态插入和删除元素。

Python的集合由dict数据类型支持，具有相同的性能特征。所有可散列的对象都可以存储在集合中。

>>> vowels = {'a', 'e', 'i', 'o', 'u'}
>>> 'e' in vowels
True

>>> letters = set('alice')
>>> letters.intersection(vowels)
{'a', 'e', 'i'}

>>> vowels.add('x')
>>> vowels
{'i', 'a', 'u', 'o', 'x', 'e'}

>>> len(vowels)
6

Python 集合和多重集合 frozenset——不可变集合

frozenset类实现了不可变版的集合，即在构造后无法更改。不可变集合是静态的，只能查询其中的元素（无法插入或删除）。因为不可变集合是静态的且可散列的，所以可以用作字典的键，也可以放置在另一个集合中，普通可变的set对象做不到这一点。

>>> vowels = frozenset({'a', 'e', 'i', 'o', 'u'})
>>> vowels.add('p')
AttributeError:
"'frozenset' object has no attribute 'add'"

# 不可变集合是可散列的，可用作字典的键
>>> d = { frozenset({1, 2, 3}): 'hello' }
>>> d[frozenset({1, 2, 3})]
'hello'

Python 集合和多重集合 collections.Counter——多重集合

Python标准库中的collections.Counter类实现了多重集合（也称背包，bag）类型，该类型允许在集合中多次出现同一个元素。

如果既要检查元素是否为集合的一部分，又要记录元素在集合中出现的次数，那么就需要用到这个类型。

>>> from collections import Counter
>>> inventory = Counter()

>>> loot = {'sword': 1, 'bread': 3}
>>> inventory.update(loot)
>>> inventory
Counter({'bread': 3, 'sword': 1})

>>> more_loot = {'sword': 1, 'apple': 1}
>>> inventory.update(more_loot)
>>> inventory
Counter({'bread': 3, 'sword': 2, 'apple': 1})

Counter类有一点要注意，在计算Counter对象中元素的数量时需要小心。调用len()返回的是多重集合中唯一元素的数量，而想获取元素的总数需要使用sum函数：

>>> len(inventory)
3 # 唯一元素的个数

>>> sum(inventory.values())
6 # 元素总数

关键要点

• 集合是Python及其标准库中含有的另一种有用且常用的数据结构。

• 查找可变集合时可使用内置的set类型。

• frozenset对象可散列且可用作字典和集合的键。

• collections.Counter实现了多重集合或“背包”类型的数据。