简介

本 PEP 提出向标准 Python 库添加一个 Set 模块，如果该模块被广泛使用，则将集合设为内置的 Python 类型。在解释了为什么集合是可取的，以及为什么使用字典代替集合的常用习惯用法不足之后，我们将描述我们打算如何使内置集合工作，以及初步的 Set 模块将如何工作。最后一节讨论集合和集合元素的可变性（或不可变性），以及 Set 模块将实现的解决方案。

基本原理

集合是基本的数学结构，在算法规范中非常常用。即使它们是“正确的”结构，它们在实现中也使用得少得多。程序员经常使用列表代替，即使列表中的排序信息无关紧要，并且按值查找很频繁。（大多数中等规模的 C 程序包含大量令人沮丧的从头到尾搜索分配的向量以确定特定项目是否存在……）

程序员经常被告知他们可以将集合实现为带有“无关”值的字典。可以通过为这些“集合”分配“无关”值来添加项目；可以使用 dict.has_key 测试成员资格；可以使用 del 删除项目。但是，集合上的其他主要操作（并集、交集和差集）不受此表示形式的直接支持，因为它们对于包含键/值对的字典来说含义不明确。

提案

本 PEP 的长期目标是向 Python 添加内置的集合类型。此类型将是唯一值的无序集合，就像字典是键/值对的无序集合一样。

迭代和推导将以显而易见的方式实现，因此

for x in S:

将以任意顺序遍历 S 的元素，而

set(x**2 for x in S)

将生成一个包含 S 中所有元素的平方的集合。成员资格将使用 in 和 not in 进行测试，基本集合操作将通过混合使用重载运算符来实现

以及方法

以及两个新的内置转换函数

注释

1. 我们建议使用按位运算符“|&”表示交集和并集。虽然“+”表示并集很直观，但“*”表示交集则不然（很少有人能正确猜出它的含义）。
2. 我们考虑使用“+”将元素添加到集合中，而不是“add”。但是，Guido van Rossum 指出“+”对于其他内置类型是对称的（虽然“*”不是）。使用“add”还可以避免该操作与集合并集之间的混淆。

集合表示法

PEP 最初建议使用 {1,2,3} 作为集合表示法，并使用 {-} 表示空集。Python 2.3 的 sets.py 的经验表明该表示法不是必需的。此外，还存在使字典不太容易识别的风险。

还考虑过大括号表示法是否支持集合推导；但是，Python 2.4 提供了生成器表达式，它完全满足了该需求，并且以更通用的方式实现了它。（有关生成器表达式的详细信息，请参阅 PEP 289）。

因此，Guido 规定不会有集合语法；但是，可以在 Python 3000 中重新审视此问题（请参阅 PEP 3000）。

历史

为了获得使用集合的经验，在 Python 2.3 中引入了纯 Python 模块。基于该实现，在 Python 2.4 中引入了 set 和 frozenset 类型。改进包括

• 改进的 frozensets 哈希算法
• 更紧凑的 pickle 格式（仅存储元素列表，而不是键：值对的字典，其中值始终为 True）。
• 使用 __reduce__ 函数，以便自动进行深度复制。
• 消除了 BaseSet 概念。
• union_update() 方法仅变成了 update()。
• 放弃了可变集合和不可变集合之间的自动转换。
• 放弃了 _repr 方法（新的 sorted() 内置函数满足了此需求）。

Tim Peters 认为类的构造函数应该接受一个序列作为参数，并使用该序列的元素填充集合。他的论点是，在大多数情况下，程序员将从预先存在的序列创建集合，因此这种情况应该是常见情况。但是，这将要求用户在使用已知值初始化集合时记住一组额外的括号

>>> Set((1, 2, 3, 4))       # case 1

另一方面，来自少数 Python 初学者（他们都非常熟悉其他语言）的反馈表明，人们会发现“无括号”语法更自然

>>> Set(1, 2, 3, 4)         # case 2

最终，我们采用了初始化程序接受单个可迭代参数的第一种策略。

可变性

本提案中最难解决的问题是集合是否应该能够包含可变元素。字典的键必须是不可变的，以便支持快速可靠的查找。虽然很容易要求集合元素是不可变的，但这将排除集合的集合（在图算法和其他应用程序中被广泛使用）。

PEP 218 的早期草案只有一个集合类型，但 Python 2.3 中的 sets.py 实现有两个，Set 和 ImmutableSet。对于 Python 2.4，新的内置类型被命名为 set 和 frozenset，它们稍微不那么笨拙。

“sets”模块中实现了两个类。Set 类的实例可以通过添加或删除元素来修改，ImmutableSet 类是“冻结”的，具有不可更改的元素集合。因此，ImmutableSet 可用作字典键或集合元素，但不能更新。两种类型的集合都要求其元素是不可变的、可散列的对象。并行注释适用于“set”和“frozenset”内置类型。

版权

本文档已置于公共领域。