引言

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

基本原理

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

程序员经常被告知他们可以将集合实现为具有“不关心”值的字典。可以通过将“不关心”值分配给它们来将项目添加到这些“集合”中；可以使用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类型。改进包括：

• frozenset的更好哈希算法
• 更紧凑的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”内置类型也适用类似的注释。

版权

本文档已置于公共领域。