运营和后台对了一次数:同一个活动页,前端埋点报表说当天有 12,480 个独立访客,后端日志去重后是 13,027。同一批请求,差了 547 个人。双方都觉得自己没错,数据也确实来自同一套日志。
把两边的明细导出来比对,第一个可疑点很快出现了:日志里的 user_id 有些是数字,有些是字符串。老系统发的是整数 10086,新接入的网关把参数当字符串透传,写成 "10086"。去重程序用的是一个普通的集合,于是同一个人被算了两次。前端那边用的是另一套语言、另一套去重实现,两边的「相等」标准还没对齐,数自然对不上。
这件事表面上是数据清洗的问题,根子上是离散数学的第一课:集合的去重效果,完全取决于元素怎么判断「相等」。而相等不是集合自带的,是元素自带的。搞不清这一点,后面所有涉及集合、关系、分组、排序的代码都会留下类似的口子。这篇就把这件事从头讲清楚:集合是什么、集合运算在做什么、笛卡尔积为什么会爆炸、关系有哪几种、以及为什么「去重」和「分组」其实是同一个动作。
集合只回答一个问题:属不属于
集合(set)可以理解成「一堆确定的对象凑成的整体」。判断某个对象在不在里面,只有一个答案:在,或者不在,没有第三种。这个判断写成 x ∈ A,读作「x 属于 A」。反过来写 x ∉ A,就是不属于。
数学定义只有两条硬约定。第一,集合里的元素没有顺序,{1, 2} 和 {2, 1} 是同一个集合。第二,集合里不重复,{1, 1, 2} 写下来还是 {1, 2}。这两条不是随手定的规矩,而是为了得到一个好用的性质,叫外延公理:两个集合相等,当且仅当它们的元素完全相同。也就是说,比较两个集合时,不需要看它们是怎么造出来的,只看最终装了哪些东西。
注意这里有个容易被跳过的前提:「元素完全相同」里的「相同」是谁定的?是元素自己。集合只负责把判断为相同的元素合并成一个,它不定义相同。整数 1 和浮点数 1.0 算不算同一个,字符串 "1" 算不算,两个内容一样的对象算不算,全是元素所在的那套类型系统说了算。
这正好解释了开头那 547 个人的差额。在 Python 里,1 == 1.0 为真,True == 1 也为真,所以它们会被合并;但 "1" == 1 为假,字符串和数字永远不会被当成同一个元素。同一份名单,混进了两种类型,集合就给出了两个答案。
ids = [1, "1", 1.0, True]
print(len(set(ids)))
print(sorted(map(repr, set(ids))))
在本机 Python 3.15 上跑,输出是:
2
["'1'", '1']
四个值最后只剩下两个:数字那一支里 1、1.0、True 被合并成了一个,字符串 "1" 单独留着。如果统计口径要求「同一个人只能算一次」,那在进集合之前,就得先把类型统一。这不是集合的错,是喂给它的数据没有满足「相等」的约定。
四种集合运算,和 SQL 里的对应
集合上最常用的运算是四个:交集、并集、差集、补集。它们的含义用一句话就能说清,难的是在代码里选对。
补集这一条值得单独说。数学教材里写 Ā,前提是先在某个范围内讨论,比如「1 到 100 的整数里,不是偶数的有哪些」。脱离全集谈补集没有意义。写代码时更明显:你没有一个包含万物的集合,只能拿一个具体的对照集合做减法。很多「取反」逻辑写错,就是因为作者脑子里有一个全集,代码里却没有。
a = {1, 2, 3, 4}
b = {3, 4, 5}
print(a & b, a | b, a - b, a ^ b)
{3, 4} {1, 2, 3, 4, 5} {1, 2} {1, 2, 5}
这四个运算在哈希集合上的平均代价都是线性的,准确说是和较小的那个集合大小成正比。所以判断「这批 ID 里有没有脏数据」时,正确做法是把白名单先建成集合,再逐个查,而不是拿列表做双重循环。后者是平方级,十万条数据就能把接口拖到超时。
笛卡尔积:所有组合,以及它为什么会爆炸
笛卡尔积(Cartesian product)是两个集合之间最朴素的组合方式:从 A 里取一个,从 B 里取一个,配成有序对,所有配法都收进来。
A × B = { (a, b) | a ∈ A, b ∈ B }
它的规模是两边大小的乘积。这一点看着无害,实际是个大坑:两个各含十万条记录的集合做笛卡尔积,结果是一百亿个有序对。这个量级不可能装进内存,也不该装。数据库里的 JOIN,语义上就是先做笛卡尔积、再按条件筛掉不符合的行;优化器做的第一件事,就是想办法避免真的把乘积算出来,比如用索引直接定位、把小表广播、按哈希分桶。你写 SELECT ... FROM a, b WHERE a.id = b.a_id 时看到的那条执行计划,本质是在讨论「怎么绕过笛卡尔积」。
代码里也是同样的道理。下面这个小例子只是两件衣服配两个尺码。
colors = ["red", "blue"]
sizes = ["S", "M"]
pairs = [(c, s) for c in colors for s in sizes]
print(pairs)
print(len(pairs))
[('red', 'S'), ('red', 'M'), ('blue', 'S'), ('blue', 'M')]
4
组合本身没错,错的是不加约束地组合。三层嵌套——用户、订单、商品,每层十万级,写出来就是一千万亿行。修法永远是先缩小集合再组合,不要指望机器扛。
关系:有序对的集合
有了笛卡尔积,关系(relation)就好定义了:它是笛卡尔积的一个子集。二元关系 R 就是从 A 到 B 的一批有序对,写成 R ⊆ A × B。说「a 和 b 有关系」,意思就是有序对 (a, b) 在 R 里。
这个定义把很多看似不同的东西统一了。「小于」是一个关系,所有满足 x 小于 y 的数对组成它的集合。「是同一个城市」是一个关系。「关注」也是一个关系。函数同样是关系,只不过多加一条限制:每个 a 只能配一个 b。所以函数是关系的一种特殊情况,反过来不成立。
二元关系有三个常用性质,判断起来都是逐对检查:
自反
每个元素都和自己有关系。写成对每个 x 都有 (x, x) 属于 R。典型例子是「等于」和「小于等于」,「小于」就不自反。
对称
只要 (a, b) 在 R 里,(b, a) 也一定在。典型例子是「是同学」,「是上级」就不对称。
传递
只要 (a, b) 和 (b, c) 都在,(a, c) 也必须在。典型例子是「小于」和「是祖先」,「关注」通常不传递。
把关系写成集合,检查性质就变成了查表。下面这段用三个有序对验证一遍。
R = {(1, 2), (2, 3), (1, 3)}
print("reflexive:", all((x, x) in R for x in (1, 2, 3)))
print("symmetric:", all((b, a) in R for (a, b) in R))
print("transitive:", all((a, c) in R for (a, b) in R for (c2, c) in R if c2 == b))
reflexive: False
symmetric: False
transitive: True
结果很直白:没有 (1, 1) 这种自指的对,所以不自反;(1, 2) 存在但 (2, 1) 不存在,所以不对称;三个对连成一条链,传递性成立。注意「传递」不是「链上每一段都在」,而是「链的两端也在」。这正是很多权限继承、组织架构、依赖检查写错的地方。
关系还有两种等价表示:一是关系矩阵,行和列都是元素,有关系的格子填 1;二是关系图,每个元素一个点,有关系就连一条边。第二种表示直接把我们带到下一篇之外的图论,也是数据库、编译器和依赖管理天天在用的结构。
等价关系与划分:去重和分组是同一个动作
三个性质里,如果自反、对称、传递同时成立,这个关系就叫等价关系。它描述的是一种「在某方面算同一类」的判断。等于是最标准的等价关系,同余、模版等价、忽略大小写后的相等也都是。
等价关系有一个很强的结论:它会把整个集合自动切成若干块,每块内部两两等价,块与块之间完全不相交,所有块并起来正好是原集合。这些块叫等价类,所有等价类组成的整体叫商集。这个切分过程叫划分。划分的两条要求——不重叠、全覆盖——正好对应等价关系的对称与自反。
所以「去重」与「分组」在数学上是同一件事:先定一个等价关系,再按等价类归并。去重是每类只留一个代表,分组是把每类装进一个桶。你在代码里写 groupby 或者写 set(),只要底层判断都是同一个等价关系,两种写法的结果就一致;一旦不一致,说明两处定义的「相等」不一样,这就是数据对不上的根源。
users = [("u1", "A@Example.com"), ("u2", "a@example.com"), ("u3", "b@example.com")]
groups = {}
for uid, email in users:
key = email.strip().lower()
groups.setdefault(key, []).append(uid)
print(groups)
{'a@example.com': ['u1', 'u2'], 'b@example.com': ['u3']}
这里定义的等价关系是「去掉首尾空白、转小写之后相同」。它显然满足自反、对称、传递,所以能切出干净的等价类。如果规则改成「编辑距离小于 2 就算同一个人」,对称性还在,但传递性通常会断:A 和 B 差一个字母,B 和 C 差一个字母,A 和 C 可能差两个。这时得到的关系不是等价关系,切出来的块会重叠,去重结果取决于你按什么顺序处理,换成并行就彻底不可复现。
偏序:为什么有些东西不能随便排
把对称换成反对称,也就是 (a, b) 和 (b, a) 最多只能有一个成立,再加上自反和传递,得到的就是偏序关系。它描述的是「谁在谁前面」,但不保证任意两个元素都能比。
依赖关系就是典型的偏序。包 A 依赖 B,B 依赖 C,于是 A 也依赖 C;但 D 和 E 之间可能毫无关系,谁先装都行。这种「有的能比、有的不能比」的结构,数学上叫偏序集。如果任意两个元素都能比,那就升级成了全序,比如数字大小。
这个区别直接决定了排序能不能做。语言内置的排序算法几乎都假设比较函数是一个全序:自反、反对称、传递。一旦你写的比较器不满足传递性,结果就不再是「不太准」,而是不可预测。Java 的 TimSort 遇到这种情况会直接抛异常,报的比较器契约被破坏;Python 和 JavaScript 则可能安静地给出一个乱序结果,等你上线后才发现列表里混进了不该出现的顺序。
真实的例子很好构造:比较器先按字符串长度比,长度相同就返回 0。「aa」和「bb」被判定相等,「bb」和「cc」也相等,但一旦混进长度为 1 的元素,前后结论就会互相打架,排序结果的稳定性完全靠运气。
要把偏序变成能排序的全序,就得补一条打破平局的规则,比如依赖相同再按名字排。这一招在工程里很常见,本质是人为地把偏序扩展成全序。如果连平局都补不出来,说明这批元素本来就没有唯一顺序,应该用拓扑排序输出「一个合法的顺序」,而不是要求排序算法给出「那个顺序」。
代码里的集合:哈希与相等的契约
数学上的集合不关心实现,代码里的集合基本都靠哈希表。哈希表要正常工作,依赖一条契约:相等的元素,哈希值必须相等;反过来不要求,哈希相同的元素可以不等,那叫碰撞,用相等判断兜底。
违反这条契约,症状很隐蔽。自定义对象只重写了相等、没重写哈希,两个内容相同的对象会被算成两个元素;哈希依赖了可变字段,对象放进集合后再改字段,哈希变了,这个元素就「失踪」了:它还在表里,但再也查不到。Java 里 hashCode 和 equals 要一起重写,Python 里定义了 __eq__ 的类默认不可哈希,都是语言在替你守这条线。
浮点数是个特殊雷区。0.1 加 0.2 不等于 0.3,这是二进制表示决定的。把浮点结果直接塞进集合去重,几乎每个值都会被当成新元素。正确做法是先明确「相等」的容差,再按容差分桶,而不是指望集合替你判断近似相等。
一张现象对照表
下面这些现象在真实项目里都出现过,原因各不相同,但都能回到集合与关系的基本定义上。
| 现象 | 真实原因 | 第一步查什么 |
|---|---|---|
| 去重后数量比预期多 | 同一实体用了不同类型或不同格式,相等判断没通过 | 把元素 repr 和类型打出来,抽样看重复项差在哪 |
| NaN 去重失败 | NaN 和任何值都不相等,包括它自己 | 先判断 isnan 并归一成一个哨兵值,再入集合 |
| 两个内容相同的对象没被合并 | 只重写了相等,没重写哈希,或哈希用了可变字段 | 检查相等与哈希是否基于同一组不可变字段 |
| 集合查找突然变慢 | 用了列表做成员判断,或哈希函数质量差导致长链 | 确认容器类型,再看哈希分布和碰撞率 |
| JOIN 把内存撑爆 | 无约束的笛卡尔积,条件写在最后才筛 | 看执行计划有没有先做乘积,条件能否提前到连接前 |
| 分组结果里同一组出现两次 | 判定规则不满足传递性,不是等价关系 | 构造三个样本验证传递性,再用并查集做闭包 |
| 排序结果偶尔乱序 | 比较器不满足全序,缺少稳定的平局规则 | 用随机数据跑多次,检查比较器是否自洽 |
边界与代价
第一,集合会丢信息。它只保留「在不在」,顺序和出现次数都没有了。要计数就得用字典或计数器,要保留原顺序就得用有序结构。很多「用集合去重再输出」的需求,其实想要的是「保留第一次出现的顺序」,这时 set 不满足,得用「字典按键去重」或者带顺序的集合实现。
第二,内存开销不小。哈希表要留空位控制碰撞率,装载因子通常在三分之二左右,每个元素还要存哈希值或索引。同样十万条数据,数组占用可能只有集合的几分之一。上到千万级,集合就不再是随手能建的东西。
第三,最坏情况不是常数级。哈希集合的平均查找是常数,但遇到对抗性构造的键,所有元素挤进同一个桶,退化回线性。对外接收用户输入当键的服务,要留意这种哈希洪水攻击,语言层面通常会加随机种子,但不是所有环境都默认开启。
第四,传递闭包很贵。朴素做法是三重循环,复杂度是元素数量的立方。元素上千就卡,上万必须换算法,或者只算需要的部分。
第五,数学上的集合是精确的,代码里的集合是近似的。浮点相等、字符串规范化、时区、编码,都会让「同一个元素」变得含糊。先把相等规则写下来,再谈去重,顺序不能反。
小结与练习
这篇的主线可以压成三句。集合只回答「属不属于」,而相等的标准由元素自己决定,所以去重前先统一口径;关系是笛卡尔积的子集,自反、对称、传递这三条决定它能切出什么样的结构;等价关系切出划分,偏序切出先后,前者对应去重和分组,后者对应依赖和排序。
下一篇讲命题逻辑与真值表。集合回答「属不属于」,逻辑回答「成立不成立」,而真值表本质上就是在给命题的真假做一张集合表。你在代码里写的每一个 if,拆到底都是一串真值判断,包括那些看起来怎么都不对的边界条件。
当天可以自己验证的练习:
- 在本机跑
set([1, "1", 1.0, True]),确认结果是 2;再用 JavaScript 跑new Set([1, "1", 1.0, true]),确认结果是 3,并解释两种语言对「相等」的定义差在哪。 - 用
float("nan")造两个 NaN,分别验证len({a, b})和a == a,再解释为什么同一个对象放进集合只算一次。 - 用两层循环生成 2 个颜色和 3 个尺码的组合,打印结果并验证长度是 6;再把外层集合扩大到一千,估算内存能不能扛住。
- 自己构造一个只有三个元素的关系集合,分别检查自反、对称、传递,并用手算结果和代码输出对照。
- 写一个「按长度比较、长度相同返回 0」的比较器,对一组字符串排序,再用随机数据跑一百次,看看结果是否每次都一样。