并查集快到像是 O(1)

并查集快到像是 O(1)
隔壁老康难度 ★★★☆☆ · 前置:数组到底快在哪 | 一句话结论:并查集的价值全在退化输入上——随机操作下三种实现看不出区别,而链式输入下朴素实现是 1 249 975 000 步,按秩合并只要 49 999 步。
五万个元素,按 0-1、1-2、2-3 的顺序依次合并,朴素并查集走了 1 249 975 000 步,1.457 秒;把这组输入的方向换个姿势,变成 0-1、0-2、0-3 的星型,步数一个不少,耗时 6.29 秒;两组都交给按秩合并版,49 999 步,1.34 毫秒。
同一条链上,朴素版和按秩版差了上千倍。两段代码加起来不到二十行。
我原来以为那个 1 249 975 000 是计数器写错了。起因是教科书上那句“路径压缩是关键优化”,我想验证它,就写了个只统计路径步数的探针,把三种实现放在同一组输入上跑:朴素、只按秩合并、按秩加压缩。第一轮用一百万个元素、一百万个随机操作,三种实现的耗时分别是 19.42、19.39、19.29 毫秒,差不到 0.7%,落在噪声里;第二轮换成链式输入,朴素版 1.457 秒,按秩版 1.34 毫秒,差了四位数,而单独加路径压缩的那一版,1 249 975 000 步,和朴素版一个字符都不差。教材习惯把两个优化并列着讲,好像必须成对出现,实测里它们的分量完全不同。
这句话我写完自己也读了两遍。
合并账号这件事
产品后台有个功能,把两个注册账号判成同一个人。用户先用手机号注册,后来又用微信登录,库里躺了两条记录,运营点一下“合并”,两条记录的历史内容、绑定支付方式、加过的群从此归到同一个身份下面;之后每次有人问“这两个账号是不是同一个人”,程序不用顺着关系图搜索,只问一件事:它们的根是不是同一个。同一类问题还有不少:一张二值化后的图片要数连通块,四邻域相邻的两个黑像素连一条边,最后看有多少个独立的团;Kruskal 建最小生成树,每加一条边先问两端是不是已经通了,通了跳过,不通就加进来。
这些事只关心两方是不是一伙的,不关心它们中间隔了多少层。
要撤销一次合并,或者把一个集合拆成两半,它做不到。这是它的边界,后面还会提。
三个动作
它的全部接口只有三个:make 建集合、find 找根、union 合并。
后面那些“压缩”“按秩”都是从这三个动作里长出来的补丁。实现用一个整数数组,p[i] 存 i 的父亲,根的父亲指向自己,这层约定很关键,所有讨论都建立在它上面。
1 | func find(p []int, x int) int { |
find 一路往上爬,直到撞见自己指自己的节点。union 找到两个根,把其中一个挂到另一个底下。
没有多余的话。
这些代码里没有一行是在防备坏输入的。
朴素版本怎么长歪
问题出在 p[ra] = rb 这个方向是固定的。输入恰好是 0-1、1-2、2-3 这样顺着来的时候,每次 union 涉及的根都是上一次新加进来的那个,于是新树根永远挂在旧树根下面,一条链越接越长;第 k 次 union 之前要先走 k 步找根,五万次累加下来就是 1.25e9 步。把它当成“最坏情况”写进复杂度分析很容易,难的是意识到这种输入真会出现:账号合并的顺序往往跟注册时间走,一次批量脚本扫表,id 递增,就是一条链。
批量导入的时候最容易撞上。
链式不是唯一的长歪方式。星型输入 0-1、0-2、0-3 也能长成链,只是方向相反,每次 union 都把当前根挂到新节点下面,find(0) 的路一样越走越长,这个细节在后面的数字里能看到痕迹。两团交替又是另一种:两个已经很深的集合来回合并,单次 find 的代价跟着轮次抬升,平均步数落在中间。
三种输入我都试了。
两种优化,各管一头
路径压缩改的是 find。
第一次找根的时候顺手把路上所有节点直接挂到根上,下次再问一步到位。它压的是这条路径,不是整棵树。按秩合并改的是 union。合并时先比较两棵树的规模,小的挂到大的下面,规模相等才让高度加一,秩只增不减,树高有上界。这两件事的作用点完全不同,一个在查询侧事后修补,一个在合并侧事前预防。
1 | func find(p []int, x int) int { |
按秩合并只多一个数组和三次比较,压缩只多一个循环,都不贵。
随机负载下谁都不差
先说不带恶意的输入。
一百万个元素,一百万个操作,一半 union 一半 find,端点用固定种子的伪随机数现取。机器是 i9-14900HX,Go 1.27.2,windows/amd64,耗时取 -count=5 的中位数,路径步数用一个 int64 计数器在 find 的循环里累加。三种实现的路径步数摊开看:
| 实现 | 总路径步数 | 平均 | 单次最大 | 耗时 |
|---|---|---|---|---|
| 朴素(不按秩不压缩) | 245 962 | 0.25 | 111 | 19.42 ms |
| 只按秩合并 | 152 593 | 0.15 | 6 | 19.39 ms |
| 按秩 + 路径压缩 | 149 588 | 0.15 | 6 | 19.29 ms |
平均每次操作 0.25 步对 0.15 步,绝对差 0.1 步,总耗时 19.42 对 19.29 毫秒,差 0.7%,落在测量噪声里。单次最大步数 111 对 6 确实好看,可它太罕见,对总数几乎没有贡献。随机 union 出来的树本来就浅:两棵随机树合并,期望高度是 log n 量级,n 是一百万也就二十层上下,而平均路径长度比高度还短得多,因为大部分节点靠近叶子,压缩在这种树上能找到的可压节点很少。
三种实现跑出来的连通分量数完全一致,我先没信,又换了组数据核对一遍,一样。
第一个反直觉的地方就在这儿:只看随机数据,这段优化代码可以不写。
三种写法都是 19 毫秒。
退化输入才见真章
换个输入,局面立刻不一样。
五万个元素,三种造树方式,每种方式跑四遍实现组合。
| 输入 | 实现 | 总路径步数 | 平均 | 最长 | 耗时 |
|---|---|---|---|---|---|
| 链式 | 朴素 | 1 249 975 000 | 24 999.50 | 49 999 | 1.457 s |
| 链式 | 只按秩 | 49 999 | 1.00 | 1 | 1.34 ms |
| 链式 | 只压缩 | 1 249 975 000 | 24 999.50 | 49 999 | 1.454 s |
| 链式 | 按秩+压缩 | 49 999 | 1.00 | 1 | 0 ms |
| 星型 | 朴素 | 1 249 975 000 | 24 999.50 | 49 999 | 6.29 s |
| 星型 | 只按秩 | 49 999 | 1.00 | 1 | 353 µs |
| 星型 | 只压缩 | 1 249 925 003 | 24 998.50 | 49 998 | 3.06 s |
| 星型 | 按秩+压缩 | 49 999 | 1.00 | 1 | 0 ms |
| 两团交替 | 朴素 | 625 000 000 | 12 500.00 | 24 999 | 1.77 s |
| 两团交替 | 只按秩 | 74 998 | 1.50 | 2 | 2.56 ms |
| 两团交替 | 只压缩 | 625 000 000 | 12 500.00 | 24 999 | 1.58 s |
| 两团交替 | 按秩+压缩 | 74 998 | 1.50 | 2 | 2.00 ms |
那个 1 249 975 000 出现了三次。
链式和星型都是五万个元素、四万九千九百九十九次 union,最坏情况累计步数是 49 999 × 50 000 / 2,算出来就是它。两个数字一模一样,因为树都是一条五万长的链,只是链的方向相反。
我盯着“只压缩”那一行看了很久,一开始以为计数器写错了。
后来想明白了:路径压缩只在 find 的时候发生,而链式 union 的每一次 find,问的都是刚刚露头的那片叶子,它下面还没有子树,压它等于压一条只有一个节点的路径,什么也没改变。等这条链长起来,中段节点早就没人再问了。换句话讲,压缩修的是已经走过的路,可链式输入每次走的都是新路。
按秩合并从源头堵住了这件事。它不让新根挂到旧根下面,而是比较规模,小的挂大的。链式输入进来,每次都是一棵几万节点的树去接一棵单节点树,单节点永远挂到下面去,树高停在 1,平均步数 1.00,最长路径 1。
星型那个 1 249 925 003 比朴素少了 49 997 步,这点差值来自压缩确实压掉了一点东西:早期几次 find(0) 走的路短,压过之后省下几步。它只占总数的十万分之四,对 3 秒的耗时没有可见影响。两团交替那组更能说明问题,按秩合并把 625 000 000 步压到 74 998 步,只压缩还是 625 000 000 步,一步没省。
连通分量也对得上:十万个元素、五万次 union,三种实现给出的分量数都是 50 001。为什么不是 50 000,因为五万次合并里有一次两端已经同属一个分量,有效合并只有 49 999 次。
这个倍数不是理论推出来的,是秒表上读出来的。
理论要两个,工程常常一个够
教科书那句“两者结合才够反阿克曼函数”没有错。
只做压缩,均摊 O(log n),单次最坏能到 Θ(n)。只做按秩合并,最坏 O(log n)。两个都做,均摊 O(α(n))。α 是反阿克曼函数,n 要大到 2 的 65536 次方那么离谱,α 才等于 5,对任何能塞进内存的 n,它都不超过 4,工程语境里的“像 O(1)”说的就是这 4 步。
问题在于理论给的是渐进上界,测出来的是具体数字。
log n 这个上界,n 等于一百万时是 20,n 等于五万时是 16。20 步和 4 步的差别确实存在,但它不会让一段 19 毫秒的代码变成 2 秒。把耗时拉开上千倍的,是链式输入把平均步数顶到 25 000,那是平方级的量,只有按秩合并能拦住。换句话说,路径压缩买的是常数因子,按秩合并买的是量级。反过来也成立。输入已经被按秩合并管住的时候,树高恒在 log n 以内,压缩带来的边际收益只剩常数;很多场景的 n 只有几千几万,log n 小于 17,压不压缩都是几十纳秒的事。两个优化都加上,代码多十行,这十行买的是不怕输入退化,这笔账怎么算都不亏。
只问是不是一伙,不问怎么连过去
判断标准能缩成一句话:只问两边是不是一伙,不问怎么连过去。要问路径、要列出中间节点、要按层次分层,用 BFS 或 DFS;要做的是动态加边、随时回答连通性,并查集最省。它不支持删除,也不支持拆分。把两条记录拆回两条,或者从分量里摘掉一个点,这个结构做不到,只能整块重建。真需要拆,有动态树那类更重的结构,代价是代码量和常数一起涨,大多数业务不值得。还有一条:只做一次性的连通块统计、输入从头到尾不变,直接 DFS 一遍往往更省事,并查集的价值在反复查询。
这些判断没有一条跟喜好有关。
回到那次一百万个元素的链式实验。我先按五万写了脚本,跑通了,顺手把参数改成一百万,以为几秒钟的事,结果 120 秒没出结果,被 kill 掉了。朴素实现在链式输入下是平方级,一百万个元素要跑几分钟,加上计数器只会更慢。五万个的链式输入 1.46 秒就跑完,一百万个是它的四百倍。
把规模缩回去之后,数据才开始说话。
能跑出结果的实验才叫实验,跑不出来的那组只能算一次提醒,它除了告诉我这里很慢,一个有效数字都没留下。
我现在写并查集,默认两个优化都加上,因为合起来不到十行。如果有人问只加一个行不行,答案是按秩合并,别指望路径压缩替你救场。前提是输入真的可能退化;随机数据下,加不加都是 19 毫秒。














