Question

“集”这个概念在 Python 中算是比较年轻的，同时它的使用率也比较低。set 和它的不可变的姊妹类型 frozenset 直到 Python 2.3 才首次以模块的形式出现，然后在 Python 2.6 中它们升级成为内置类型。

　本书中“集”或者“集合”既指 set，也指 frozenset。当“集”仅指代 set 类时，我会用等宽字体表示 9。

9“集”在英文中就是 set，因此原书中需要用等宽字体来区分特指和泛指。——编者注

集合的本质是许多唯一对象的聚集。因此，集合可以用于去重：

>>> l = ['spam', 'spam', 'eggs', 'spam']
>>> set(l)
{'eggs', 'spam'}
>>> list(set(l))
['eggs', 'spam']

集合中的元素必须是可散列的，set 类型本身是不可散列的，但是 frozenset 可以。因此可以创建一个包含不同 frozenset 的 set。

除了保证唯一性，集合还实现了很多基础的中缀运算符。给定两个集合 a 和 b，a | b 返回的是它们的合集，a & b 得到的是交集，而 a - b 得到的是差集。合理地利用这些操作，不仅能够让代码的行数变少，还能减少 Python 程序的运行时间。这样做同时也是为了让代码更易读，从而更容易判断程序的正确性，因为利用这些运算符可以省去不必要的循环和逻辑操作。

例如，我们有一个电子邮件地址的集合（haystack），还要维护一个较小的电子邮件地址集合（needles），然后求出 needles 中有多少地址同时也出现在了 heystack 里。借助集合操作，我们只需要一行代码就可以了（见示例 3-10）。

示例 3-10　needles 的元素在 haystack 里出现的次数，两个变量都是 set 类型

found = len(needles & haystack)

如果不使用交集操作的话，代码可能就变成了示例 3-11 里那样。

示例 3-11　needles 的元素在 haystack 里出现的次数（作用和示例 3-10 中的相同）

found = 0
for n in needles:
  if n in haystack:
    found += 1

示例 3-10 比示例 3-11 的速度要快一些；另一方面，示例 3-11 可以用在任何可迭代对象 needles 和 haystack 上，而示例 3-10 则要求两个对象都是集合。话再说回来，就算手头没有集合，我们也可以随时建立集合，如示例 3-12 所示。

示例 3-12　needles 的元素在 haystack 里出现的次数，这次的代码可以用在任何可迭代对象上

found = len(set(needles) & set(haystack))

# 另一种写法：
found = len(set(needles).intersection(haystack))

示例 3-12 里的这种写法会牵扯到把对象转化为集合的成本，不过如果 needles 或者是 haystack 中任意一个对象已经是集合，那么示例 3-12 的方案可能就比示例 3-11 里的要更高效。

以上的所有例子的运行时间都能在 3 毫秒左右，在含有 10 000 000 个元素的 haystack 里搜索 1000 个值，算下来大概是每个元素 3 微秒。

除了速度极快的查找功能（这也得归功于它背后的散列表），内置的 set 和 frozenset 提供了丰富的功能和操作，不但让创建集合的方式丰富多彩，而且对于 set 来讲，我们还可以对集合里已有的元素进行修改。在讨论这些操作之前，先来看一下相关的句法。

3.8.1　集合字面量

除空集之外，集合的字面量——{1}、{1, 2}，等等——看起来跟它的数学形式一模一样。如果是空集，那么必须写成 set() 的形式。

　句法的陷阱

不要忘了，如果要创建一个空集，你必须用不带任何参数的构造方法 set()。如果只是写成 {} 的形式，跟以前一样，你创建的其实是个空字典。

在 Python 3 里面，除了空集，集合的字符串表示形式总是以 {...} 的形式出现。

>>> s = {1}
>>> type(s)
<class 'set'>
>>> s
{1}
>>> s.pop()
1
>>> s
set()

像 {1, 2, 3} 这种字面量句法相比于构造方法（set([1, 2, 3])）要更快且更易读。后者的速度要慢一些，因为 Python 必须先从 set 这个名字来查询构造方法，然后新建一个列表，最后再把这个列表传入到构造方法里。但是如果是像 {1, 2, 3} 这样的字面量，Python 会利用一个专门的叫作 BUILD_SET 的字节码来创建集合。

用 dis.dis（反汇编函数）来看看两个方法的字节码的不同：

>>> from dis import dis
>>> dis('{1}')                  ➊
  1       0 LOAD_CONST       0 (1)
        3 BUILD_SET        1    ➋
        6 RETURN_VALUE
>>> dis('set([1])')               ➌
  1       0 LOAD_NAME        0 (set)  ➍
        3 LOAD_CONST       0 (1)
        6 BUILD_LIST       1
        9 CALL_FUNCTION      1 (1 positional, 0 keyword pair)
       12 RETURN_VALUE

➊ 检查 {1} 字面量背后的字节码。

➋ 特殊的字节码 BUILD_SET 几乎完成了所有的工作。

➌ set([1]) 的字节码。

➍ 3 种不同的操作代替了上面的 BUILD_SET：LOAD_NAME、BUILD_LIST 和 CALL_FUNCTION。

由于 Python 里没有针对 frozenset 的特殊字面量句法，我们只能采用构造方法。Python 3 里 frozenset 的标准字符串表示形式看起来就像构造方法调用一样。来看这段控制台对话：

>>> frozenset(range(10))
frozenset({0, 1, 2, 3, 4, 5, 6, 7, 8, 9})

既然提到了句法，就不得不提一下我们已经熟悉的列表推导，因为也有类似的方式来新建集合。

3.8.2　集合推导

Python 2.7 带来了集合推导（setcomps）和之前在 3.2 节里讲到过的字典推导。示例 3-13 是个简单的例子。

示例 3-13　新建一个 Latin-1 字符集合，该集合里的每个字符的 Unicode 名字里都有“SIGN”这个单词

>>> from unicodedata import name  ➊
>>> {chr(i) for i in range(32, 256) if 'SIGN' in name(chr(i),'')}  ➋
{'§', '=', '¢', '#', '¤', '<', '¥', 'μ', '×', '$', '¶', '£', '©',
'°', '+', '÷', '±', '>', '¬', '®', '%'}

➊ 从 unicodedata 模块里导入 name 函数，用以获取字符的名字。

➋ 把编码在 32~255 之间的字符的名字里有“SIGN”单词的挑出来，放到一个集合里。

跟句法相关的内容就讲到这里，下面看看用于集合类型的丰富操作。

3.8.3　集合的操作

图 3-2 列出了可变和不可变集合所拥有的方法的概况，其中不少是运算符重载的特殊方法。表 3-2 则包含了数学里集合的各种操作在 Python 中所对应的运算符和方法。其中有些运算符和方法会对集合做就地修改（像 &=、difference_update，等等），这类操作在纯粹的数学世界里是没有意义的，另外 frozenset 也不会实现这些操作。

图 3-2：collections.abc 中，MutableSet 和它的超类的 UML 类图（箭头从子类指向超类，抽象类和抽象方法的名称以斜体显示，其中省略了反向运算符方法）

　表 3-2 中的中缀运算符需要两侧的被操作对象都是集合类型，但是其他的所有方法则只要求所传入的参数是可迭代对象。例如，想求 4 个聚合类型 a、b、c 和 d 的合集，可以用 a.union(b, c, d)，这里 a 必须是个 set，但是 b、c 和 d 则可以是任何类型的可迭代对象。

表3-2：集合的数学运算：这些方法或者会生成新集合，或者会在条件允许的情况下就地修改集合

数学符号

Python运算符

方法

描述

S ∩ Z

s & z

s.\_\_and\_\_(z)

s 和 z 的交集

z & s

s.\_\_rand\_\_(z)

反向 & 操作

s.intersection(it, ...)

把可迭代的 it 和其他所有参数转化为集合，然后求它们与 s 的交集

s &= z

s.\_\_iand\_\_(z)

把 s 更新为 s 和 z 的交集

s.intersection\_update(it, ...)

把可迭代的 it 和其他所有参数转化为集合，然后求得它们与 s 的交集，然后把 s 更新成这个交集

S ∪ Z

s | z

s.\_\_or\_\_(z)

s 和 z 的并集

z | s

s.\_\_ror\_\_(z)

| 的反向操作

s.union(it, ...)

把可迭代的 it 和其他所有参数转化为集合，然后求它们和 s 的并集

s |= z

s.\_\_ior\_\_(z)

把 s 更新为 s 和 z 的并集

s.update(it, ...)

把可迭代的 it 和其他所有参数转化为集合，然后求它们和 s 的并集，并把 s 更新成这个并集

S \ Z

s - z

s.\_\_sub\_\_(z)

s 和 z 的差集，或者叫作相对补集

z - s

s.\_\_rsub\_\_(z)

- 的反向操作

s.difference(it, ...)

把可迭代的 it 和其他所有参数转化为集合，然后求它们和 s 的差集

s -= z

s.\_\_isub\_\_(z)

把 s 更新为它与 z 的差集

s.difference\_update(it, ...)

把可迭代的 it 和其他所有参数转化为集合，求它们和 s 的差集，然后把 s 更新成这个差集

s.symmetric\_difference(it)

求 s 和 set(it) 的对称差集

S △ Z

s ^ z

s.\_\_xor\_\_(z)

求 s 和 z 的对称差集

z ^ s

s.\_\_rxor\_\_(z)

^ 的反向操作

s.symmetric\_difference\_update(it, ...)

把可迭代的 it 和其他所有参数转化为集合，然后求它们和 s 的对称差集，最后把 s 更新成该结果

s ^= z

s.\_\_ixor\_\_(z)

把 s 更新成它与 z 的对称差集

　在写这本书的时候，Python 有个缺陷（issue 8743），里面说到 set() 的运算符（or、and、sub、xor 和它们相对应的就地修改运算符）要求参数必须是 set() 的实例，这就导致这些运算符不能被用在 collections.abc.Set 这个子类上面。这个缺陷已经在 Python 2.7 和 Python 3.4 里修复了，在你看到这本书的时候，它已经成了历史。

表 3-3 里列出了返回值是 True 和 False 的方法和运算符。

表3-3：集合的比较运算符，返回值是布尔类型

数学符号	Python 运算符	方法	描述
		s.isdisjoint(z)	查看 s 和 z 是否不相交（没有共同元素）
e ∈ S	e in s	s.\_\_contains\_\_(e)	元素 e 是否属于 s
S ⊆ Z	s <= z	s.\_\_le\_\_(z)	s 是否为 z 的子集
		s.issubset(it)	把可迭代的 it 转化为集合，然后查看 s 是否为它的子集
		S ⊂ Z	s < z	s.\_\_lt\_\_(z)	s 是否为 z 的真子集
		S ⊇ Z	s >= z	s.\_\_ge\_\_(z)	s 是否为 z 的父集
				s.issuperset(it)	把可迭代的 it 转化为集合，然后查看 s 是否为它的父集
				S ⊃ Z	s > z	s.\_\_gt\_\_(z)	s 是否为 z 的真父集

除了跟数学上的集合计算有关的方法和运算符，集合类型还有一些为了实用性而添加的方法，其汇总见于表 3-4。

表3-4：集合类型的其他方法

	set	frozenset
s.add(e)	•		把元素 e 添加到 s 中
s.clear()	•		移除掉 s 中的所有元素
s.copy()	•	•	对 s 浅复制
s.discard(e)	•		如果 s 里有 e 这个元素的话，把它移除
s.__iter__()	•	•	返回 s 的迭代器
s.__len__()	•	•	len(s)
s.pop()	•		从 s 中移除一个元素并返回它的值，若 s 为空，则抛出 KeyError 异常
s.remove(e)	•		从 s 中移除 e 元素，若 e 元素不存在，则抛出 KeyError 异常

到这里，我们差不多把集合类型的特性总结完了。

下面会继续探讨字典和集合类型背后的实现，看看它们是如何借助散列表来实现这些功能的。读完这章余下的内容后，就算再遇到 dict、set 或是其他这一类型的一些莫名其妙的表现，你也不会手足无措。