说实话我做技术这么多年对随机化算法最深的感触来自一次线上事故一个负责排序的服务在压测时延迟突然飙升排查到最后发现请求里刚好带了近乎升序排列的数据而排序实现用的是固定取第一个元素的快速排序。直接退化成 O(n²)直接把 CPU 打满。那一刻我才意识到确定性方案在遭遇针对性输入时有多脆弱。后来我在关键路径里换成了随机化算法问题再没出现过。这篇文章想系统聊聊这条技术路线——它为什么有效、两大核心范式怎么选、经典算法的概率分析怎么做以及工程落地时那些文档里不会明说的坑。1. 蒙特卡洛与拉斯维加斯随机化算法的两大范式很多人对随机化算法的第一印象是“不靠谱”但实际上随机化算法从不追求“每一步都确定”而是在“结果正确性”和“运行效率”之间做交易。理解它的起点是先分清两条技术路线拉斯维加斯型Las Vegas和蒙特卡洛型Monte Carlo。这两个名字都来自赌城但性质完全不同。拉斯维加斯型算法的特点是结果永远正确只是运行时间不确定。随机化快速排序是典型代表。无论随机数怎么生成最终返回的数组一定是有序的——随机性只影响它花了多少时间。随机化快速选择算法同理它一定能找到第 k 小的元素只是比较次数可能多可能少。这类算法的核心价值在于它能用随机性“粉碎”最坏输入让攻击或巧合构造的坏数据无法稳定触发最坏复杂度但输出始终可靠。蒙特卡洛型算法则相反运行时间固定结果有小概率出错。最经典的例子是素性测试。米勒-拉宾算法在判定一个数是素数时单次测试有 1/4 的概率把合数误判成素数不会把素数误判为合数。但通过独立重复测试错误率可以降到极低。蒙特卡洛积分也是这个思路——用随机采样近似定积分值采样点越多结果越接近真实值而不是精确值。两种范式没有绝对的优劣。我在实际项目里会按如下标准选择范式结果正确性运行时间典型例子适用场景拉斯维加斯始终正确随机随机化快排、随机化选择、Treap结果不可复核必须绝对正确蒙特卡洛可容忍小概率错误固定素性测试、蒙特卡洛积分、抽查结果可接受近似或可外部校验一个容易被忽略的判断标准是“结果能不能被低成本复核”。比如在一个推荐系统的候选生成阶段如果用一个近似算法返回候选集下游还有精排模型兜底那蒙特卡洛的微小误差完全没影响但如果是在交易对账、审计日志这种“一笔数据都错不起”的场景哪怕错误率只有万分之一也值得三思尽量改用拉斯维加斯或者做一次确定性校验。1.1 为什么“随机”能对抗“坏输入”理解随机化算法的威力核心在于一个洞察坏情况如有序数组导致快排退化之所以存在是因为固定规则给了输入数据一个明确的“攻击点”。固定取第一个元素当主元只要攻击者或巧合构造一个升序数组每一次分区都会退化成极端不平衡的划分——左边为空右边为 n-1 个元素。这不是算法实现太差而是确定性策略天然存在这样的结构缺陷而且可以被精确预测。随机化之后情况完全不同。主元的选取由一个随机过程决定输入数据并不知道这次运行会抽到哪个位置。即使数据整体上有某种偏向它也无法保证每次都能抽中最坏的那个元素。更准确地说最坏输入不再与某个具体输入绑定而是与一次非常不走运的随机数序列绑定。而随机数序列出现极端情况的概率是可以被概率论工具精确控制的。这就像打牌时把牌洗乱再发就算牌本身有规律洗牌之后你也不知道每家拿到什么牌。输入可以精心构造但它猜不中随机数生成器这一局的输出。这就是随机化算法对“对抗性输入”免疫的根本原理。2. 随机化快速排序的期望复杂度是怎么算出来的随机化算法不能在工程里只凭感觉用还得算得清楚。我以随机化快速排序为例完整做一次期望复杂度分析。这个推导思路不仅仅是考试题它能帮你理解“随机化带来了什么保证”。2.1 固定主元为何会被“定向爆破”先看确定性快排的痛点。每次选区间第一个元素做主元如果输入是升序数组第一次分区选到最小值右区间剩下 n-1 个元素第二次又选到剩余区间的最小值右区间剩下 n-2 个……比较次数是C (n-1) (n-2) ... 1 n(n-1)/2也就是 O(n²)。处理十万个有序元素时这十万次比较量级会从百万级别跳升到十亿级别延迟自然崩掉。更麻烦的是这不是“极端用例”而是任何有序数据都可能触发的常态。2.2 用指示变量把期望比较次数算明白这里引入一套经典的概率分析打法。假设数组排序完成后结果为 z₁ z₂ ... zₙ从小到大排列。定义指示变量 X_{ij}如果 zᵢ 和 zⱼ 在排序过程中被直接比较过则 X_{ij}1否则为 0。总比较次数就是 C Σ X_{ij}所有 ij 的组合求和。为什么“直接比较”这个定义很方便因为在快速排序里任意一对元素最多只会被比较一次。第一次分区之后它们要么被分进同一个子区间继续比较要么从此永远分开。如果它们至今没被比较过后续也不可能再被比较了。关键在于计算被比较的概率。考虑从 zᵢ 到 zⱼ 这段连续区间长度是 j-i1。在这段区间第一次被选为 pivot 之前这 j-i1 个元素一直在同一个递归子问题里。只有两种情况会发生直接比较第一次选的主元恰好是 zᵢ或者恰好是 zⱼ。如果第一次选中的是中间某个元素那么 zᵢ 和 zⱼ 会被划分到以该主元为界的两个不同子区间从此再也没有机会比较。主元选择是均匀随机的所以P(X_{ij}1) 2 / (j-i1)由此期望比较次数为E[C] Σ_{1≤ij≤n} P(X_{ij}1) Σ_{1≤ij≤n} 2/(j-i1)令 d j-i这个式子里 d 从 1 到 n-1每组 d 对应 n-d 对元素。于是E[C] 2 Σ_{d1}^{n-1} (n-d)/(d1) ≤ 2n Σ_{d1}^{n-1} 1/(d1) O(n log n)这是一个非常漂亮的结论无论输入数据是什么顺序期望比较次数都压在 O(n log n)。注意它没有说“每一次运行都一定是 O(n log n)”而是说如果我们重复跑很多次平均来看就是 O(n log n)运气极端差导致退化的概率极其低而且可以通过调整随机化策略进一步压低。2.3 工程实现里的随机主元细节理论归理论工程上写随机化快排时还有几个容易踩的细节。一是随机主元的选取成本。每次分区都调用一次随机数生成对于动辄上亿元素的排序任务这会引入额外的开销。常见的折中方案是先对整个数组做一次洗牌再跑确定性快排或者只在外层递归层面随机化。洗牌的开销也是 O(n)整体复杂度不增加但实现更简单而且随机性提前注入完毕后面递归过程无需再调用随机数生成器。二是随机数生成器的范围要严谨。生成一个 [left, right] 区间的随机下标注意边界不能越界。用random.randint(left, right)这类 API 时要清楚它是闭区间还是开区间很多线上 bug 就出在 left1 还是 left 的边界判断上。三是递归深度问题。随机化快排的最坏递归深度在极端情况下仍然可能达到 O(n)但概率极低。在一些对栈深度敏感的嵌入式环境或受限运行时里我习惯在递归层数超过某个阈值时切换为堆排序作为兜底策略。业界很多优秀排序库就是这么干的比如那种“快排 堆排兜底 插入排序收尾”的组合设计。3. 蓄水池抽样数据流里的均匀抽样如果说随机化快排是“用随机换效率”那蓄水池抽样就是“用随机换内存”。3.1 问题边界与直觉先描述问题一个长度未知的数据流可能非常大甚至无穷无尽要求只能遍历一次从中抽取 k 个元素且保证抽出来的 k 个元素是均匀随机的。换句话说数据流走到第 N 个元素时任意一个已经见过的元素被选入最终样本的概率都必须是 k/N。朴素做法把所有数据全部存下来再抽内存 O(N)数据量大时直接不可行。蓄水池抽样只需要 O(k) 的内存就能在流式环境下完成均匀抽样而且实现逻辑极短。算法描述如下先把前 k 个元素全部放入“蓄水池”一个长度为 k 的数组。从第 i 个元素开始i k生成一个 [0, i) 的随机整数 r如果 r k则用当前元素替换池中下标为 r 的元素否则跳过当前元素。看起来非常反直觉——一个新的元素以 k/i 的概率进池同时又随机挤掉池里一个老元素。为什么这样能做到均匀3.2 归纳法证明我建议所有读到这里的朋友先自己推一遍这是个特别好的概率论练习。证明用归纳法维持一个不变量处理完前 i 个元素后前 i 个元素中任意一个仍然留在池子里的概率都是 k/i。当 i k 时前 k 个元素都被直接放入池中概率 1 k/k基例成立。假设处理完前 i-1 个元素时前 i-1 个元素中任意一个留在池中的概率是 k/(i-1)。现在处理第 i 个元素。对于一个此前已经在池中的元素 e它在处理第 i 个元素后仍然在池中的概率为它在 i-1 时刻仍在池中概率 k/(i-1)且在第 i 个元素被选中进入池时没有被替换掉。第 i 个元素进入池中的概率是 k/i进入后随机占一个下标占中 e 的具体下标的概率是 1/k。因此 e 被替换的概率是 (k/i) × (1/k) 1/i。保留概率为(k/(i-1)) × (1 - 1/i) (k/(i-1)) × ((i-1)/i) k/i至于第 i 个新元素它进入池中的概率本来就被设计为 k/i。所以处理完 i 个元素后所有元素留在池中的概率都是 k/i。当数据流走完时每个元素被选入样本的概率为 k/N满足均匀性要求。这段证明的巧妙之处在于它不要求你知道 N 是多少也不要求中途改变策略一个简单的“持续替换”就能让所有历史元素维持相同的入选概率。在线算法能做到这一点确实让人有种“设计得很优雅”的感慨。3.3 工程示例与扩展用 Python 实现只需要十几行import random def reservoir_sample(stream, k): reservoir [] for i, item in enumerate(stream): if i k: reservoir.append(item) else: r random.randint(0, i) if r k: reservoir[r] item return reservoir这里random.randint(0, i)生成闭区间 [0, i] 的整数配合条件r k刚好模拟了“以 k/(i1) 概率替换”的行为注意下标细节即可。在实际工作中我遇到过两种衍生需求值得展开。一是加权蓄水池抽样。数据流里的每个元素权重不同比如日志里有些来源出现频率高有些低希望样本比例按权重而非元素个数来。朴素做法是把每个元素复制成权重份再抽但权重可能很大复制不现实。业界常用“指数跳跃”变体生成随机指数分布变量来决定每个元素应该“占据”多少虚构位置这样无需展开权重数组也能得到加权均匀样本。这块内容稍微有些深很多网上的实现其实都没考虑权重一致性需要格外谨慎。二是分布式环境下的抽样合并。多台机器各自处理一部分数据流每台生成局部样本之后如果想合并成全局均匀样本不能简单拼接。一种可行方案是每个元素进入全局候选的阈值取决于全局唯一哈希值比如对每个元素生成 [0,1) 随机数保留前 k 小的各路候选收集后归并排序取前 k 个。这样所有机器可以在不通信的情况下产出可合并的样本这也是很多日志采样系统的底层思路。4. 概率结构的启发布隆过滤器的误报控制说到随机化算法在工程系统里最广泛的渗透我觉得不得不提概率数据结构。布隆过滤器虽然不是严格意义上的“随机化算法”——它的哈希函数往往是确定性的——但它把“容忍小概率误差以换取空间和时间”的思路用到了极致和蒙特卡洛范式在哲学上一脉相承。4.1 位数组与哈希函数的组合布隆过滤器的核心结构是一个长度为 m 位的数组全部初始化为 0配 k 个相互独立的哈希函数。插入一个元素时用 k 个哈希函数分别算出 k 个位置全部置 1。查询一个元素是否存在时检查这 k 个位置是否全部为 1如果有任一位置为 0则元素一定不在集合中如果全部为 1则元素可能在集合中也可能误报实际上不存在但位被其他元素置了 1。所以布隆过滤器有个鲜明的特性它没有假阴性只有假阳性。不存在的情况绝不会被漏判存在的情况绝不会被判成不存在但“不存在但被误判为存在”是可能的。这个不对称性让它在很多业务里变得非常实用。比方说做缓存穿透防护请求来的时候先问布隆过滤器一个 key 如果过滤器说“一定不存在”那就直接返回空根本不必去查慢存储。只有过滤器说“可能存在”时才放行到真实存储。由于不存在假阴性布隆过滤器不会漏掉任何真实存在的 key最多是多放行几个本不存在的请求这些请求会被真实存储挡住不会造成错误返回。4.2 误报率公式与参数选择误报率是布隆过滤器最核心的指标。推导并不复杂值得自己算一遍。一个元素经过一个哈希函数后某个特定比特位被置 1 的概率是 1/m不被置 1 的概率是 1 - 1/m。插入 n 个元素、每个元素使用 k 个独立的哈希函数后这个比特位仍然为 0 的概率近似为(1 - 1/m)^(kn) ≈ e^(-kn/m)查询一个不在集合中的元素时它对应的 k 个位置全为 1 的概率就是P(误报) (1 - e^(-kn/m))^k这个公式直接告诉我们两件事误报率随 m/n每个元素占用的比特数增大而下降误报率随 k 的变大不是单调变化的——哈希函数太少碰撞多太多位数组被快速填满。存在一个最优 k 值k ≈ (m/n) × ln 2此时 e^(-kn/m) 1/2误报率降到最低约为 (1/2)^k。我常用这张表来做参数粗选m/n每元素比特数最优哈希函数数 k最低误报率4约 3约 14.7%8约 6约 2.1%16约 11约 0.08%32约 22约 1e-7工程上我一般从 m/n 8 起步也就是每个元素大概 1 字节的位空间误报约 2%对很多过滤场景足够对准确率要求更高的直接上 16 甚至 32。4.3 业务里的用量估算和重建实际选参数时还要考虑集合大小 n 的预估。如果 n 估小了位数组实际塞进更多元素误报率会显著上升估大了空间浪费。有个经验方法先拍一个 n 的上限然后决定能接受的误报率上限反推 m 和 k。要注意的是哈希函数的选择。很多实现直接拿两个基础哈希值做线性组合来模拟多个哈希函数比如 h_i(x) h1(x) i * h2(x)这种方案在工程上广泛使用性能高很多但要注意 h1、h2 的取值空间和最终取模要尽量均匀否则某些 i 组合会产生强烈相关性影响误报率。另一个经常被忽略的设计点是“能不能删除”。标准布隆过滤器不能删除元素因为无法区分某个位到底是被哪个元素置 1 的。如果业务需要支持删除就得换成计数布隆过滤器用计数器数组代替位数组删除时做计数器减一。代价是空间膨胀好几倍还要防止计数器溢出。我自己的经验是大多数只需要“去重判负”的场景标准布隆过滤器就够了需要完整增删的场景不如考虑布谷鸟过滤器或 Count-Min Sketch 这类更复杂的结构别一上来就套布隆过滤器。5. 工程里的随机化“暗坑”种子、复现与测试随机化算法在纸面上非常优雅但接入真实系统时那些“概率分析里不会写”的工程细节往往才是决定成败的部分。我在多个项目里踩过坑这里整理成几条实战经验。5.1 随机数源伪随机与真随机的权衡先说随机数源。算法设计时我们假设有完美的独立均匀随机源但真实世界的随机数都是生成的而且大多数是伪随机数——用一个确定性序列模拟随机性。绝大多数场景下质量合格的伪随机数生成器如很多现代语言标准库里的实现完全够用因为算法的概率分析依赖的是“均匀性”和“独立性”而不是“不可预测性”。只有两种情况需要考虑更高级的随机源一是安全相关场景比如生成密钥、令牌或抽奖防作弊此时不仅要均匀还要防预测应该从系统熵源取数二是某些老旧的、质量很差的随机数实现比如早期某些平台的标准库随机数存在明显的低位周期问题直接用于抽样可能导致结果分布不均匀。如果拿不准就做一次简单统计检验生成几万个随机数分桶统计频次看看每个桶的波动是否符合预期。5.2 可复现性种子记录与重放随机化算法带来的一个非常实际的工程麻烦是同样的输入两次运行可能输出不同结果。这在开发调试时尤其头疼——一个 bug 可能在一次运行中复现、下一次运行消失。我的做法是在所有需要随机化的入口处支持显式指定随机种子seed。上线时种子从高熵源取得测试和 debug 时固定一个种子让行为完全可复现。具体来说抽样式任务比如日志抽样、AB 实验分配在任务配置里记录“本次使用的种子”对账、审计类场景把种子作为元数据写入结果方便事后重放验证单元测试里不要用time()或random全局默认种子固定一个常量种子再跑确保 CI 回归稳定。这样既能保留随机化带来的抗对抗输入能力又保留了确定性的可调试性。种子机制是可复现随机化的基础和底线。5.3 测试随机化代码的正确打开方式随机化算法的测试方法和确定性算法完全不同。如果你写了一个随机化快排普通单元测试断言“排序结果正确”没问题但它不会告诉你随机化是否真的均匀也不会暴露“某一种随机序列会让算法退化”的边界问题。我一般分三层做测试第一层正确性测试。固定种子跑各种输入全升序、全降序、大量重复、空数组、单元素断言结果绝对正确。这一层不关心随机性只关心“结果不能错”。第二层统计性质测试。对蓄水池抽样这类算法跑很多次统计每个元素被选中的频率做卡方检验或简单的比例偏差检查。比如从 1 到 10 的流中抽 1 个元素跑一万次检查每个数字被抽中的次数是否都在 1000 上下。偏差超过几个百分点说明随机源或算法实现有问题。第三层压力与对抗测试。对随机化快排构造能触发确定性版本最坏情况的输入有序数组及其各种变形反复跑很多遍确认没有出现 O(n²) 级退化。这个测试的核心思路是坏输入或许存在但必须证明它无法稳定触发坏情况。有一点务必要提醒对蒙特卡洛类算法单次运行断言结果“正确”是毫无意义的因为结果可能以一定概率错误。正确的测试姿势是观测长时间、多轮次后的错误率是否与理论一致。比如测素性测试就构造一批已知合数重复跑几百次统计误判次数确认比例在理论范围内。一次两次误判不是 bug错误率显著高于理论值那才是 bug。6. 我在实际项目中应用随机化算法的几点体会这篇博文几乎写成了一个小型专题但如果你只带走一样东西我希望是随机化不是你逃避确定性的借口而是你对抗那些“刻意设计的坏输入”和“高昂的最坏代价”时概率分析能帮你算得清清楚楚的工程武器。就我的经验入门阶段最值得先练两个手写实现和两个证明手写随机化快排并推导它的期望比较次数手写蓄水池抽样并证明它的均匀性。这两个基础题吃透之后你对随机化的敏感度会明显不一样。之后再碰到像布隆过滤器这类概率结构就能自然联想到背后的误报率公式而不是停留在“大概有用”的层面。我踩过几次坑之后形成了三条铁律式的习惯第一任何随机化算法的入口都要留种子注入接口永远给可复现性留后路第二上线之前必须做统计性质测试只断言单次“结果对”是远远不够的第三不要把蒙特卡洛算法用在结果不可复核、又没有兜底校验的关键交易链路里。遵守这三条随机化算法几乎不会给你惹祸。另外还要说一点随机化算法不是万能的。它能压低最坏情况出现的概率但没法从原理上彻底消灭它。如果你的系统对延迟的“最坏情况”有硬性要求比如实时交易系统里任何一次超时都不可接受那么即使随机化快排的退化概率已经被压到极低你可能还是需要搭配其他机制。理解这一点才能避免把概率分析当成偷懒的借口。
说实话我做技术这么多年对随机化算法最深的感触来自一次线上事故一个负责排序的服务在压测时延迟突然飙升排查到最后发现请求里刚好带了近乎升序排列的数据而排序实现用的是固定取第一个元素的快速排序。直接退化成 O(n²)直接把 CPU 打满。那一刻我才意识到确定性方案在遭遇针对性输入时有多脆弱。后来我在关键路径里换成了随机化算法问题再没出现过。这篇文章想系统聊聊这条技术路线——它为什么有效、两大核心范式怎么选、经典算法的概率分析怎么做以及工程落地时那些文档里不会明说的坑。1. 蒙特卡洛与拉斯维加斯随机化算法的两大范式很多人对随机化算法的第一印象是“不靠谱”但实际上随机化算法从不追求“每一步都确定”而是在“结果正确性”和“运行效率”之间做交易。理解它的起点是先分清两条技术路线拉斯维加斯型Las Vegas和蒙特卡洛型Monte Carlo。这两个名字都来自赌城但性质完全不同。拉斯维加斯型算法的特点是结果永远正确只是运行时间不确定。随机化快速排序是典型代表。无论随机数怎么生成最终返回的数组一定是有序的——随机性只影响它花了多少时间。随机化快速选择算法同理它一定能找到第 k 小的元素只是比较次数可能多可能少。这类算法的核心价值在于它能用随机性“粉碎”最坏输入让攻击或巧合构造的坏数据无法稳定触发最坏复杂度但输出始终可靠。蒙特卡洛型算法则相反运行时间固定结果有小概率出错。最经典的例子是素性测试。米勒-拉宾算法在判定一个数是素数时单次测试有 1/4 的概率把合数误判成素数不会把素数误判为合数。但通过独立重复测试错误率可以降到极低。蒙特卡洛积分也是这个思路——用随机采样近似定积分值采样点越多结果越接近真实值而不是精确值。两种范式没有绝对的优劣。我在实际项目里会按如下标准选择范式结果正确性运行时间典型例子适用场景拉斯维加斯始终正确随机随机化快排、随机化选择、Treap结果不可复核必须绝对正确蒙特卡洛可容忍小概率错误固定素性测试、蒙特卡洛积分、抽查结果可接受近似或可外部校验一个容易被忽略的判断标准是“结果能不能被低成本复核”。比如在一个推荐系统的候选生成阶段如果用一个近似算法返回候选集下游还有精排模型兜底那蒙特卡洛的微小误差完全没影响但如果是在交易对账、审计日志这种“一笔数据都错不起”的场景哪怕错误率只有万分之一也值得三思尽量改用拉斯维加斯或者做一次确定性校验。1.1 为什么“随机”能对抗“坏输入”理解随机化算法的威力核心在于一个洞察坏情况如有序数组导致快排退化之所以存在是因为固定规则给了输入数据一个明确的“攻击点”。固定取第一个元素当主元只要攻击者或巧合构造一个升序数组每一次分区都会退化成极端不平衡的划分——左边为空右边为 n-1 个元素。这不是算法实现太差而是确定性策略天然存在这样的结构缺陷而且可以被精确预测。随机化之后情况完全不同。主元的选取由一个随机过程决定输入数据并不知道这次运行会抽到哪个位置。即使数据整体上有某种偏向它也无法保证每次都能抽中最坏的那个元素。更准确地说最坏输入不再与某个具体输入绑定而是与一次非常不走运的随机数序列绑定。而随机数序列出现极端情况的概率是可以被概率论工具精确控制的。这就像打牌时把牌洗乱再发就算牌本身有规律洗牌之后你也不知道每家拿到什么牌。输入可以精心构造但它猜不中随机数生成器这一局的输出。这就是随机化算法对“对抗性输入”免疫的根本原理。2. 随机化快速排序的期望复杂度是怎么算出来的随机化算法不能在工程里只凭感觉用还得算得清楚。我以随机化快速排序为例完整做一次期望复杂度分析。这个推导思路不仅仅是考试题它能帮你理解“随机化带来了什么保证”。2.1 固定主元为何会被“定向爆破”先看确定性快排的痛点。每次选区间第一个元素做主元如果输入是升序数组第一次分区选到最小值右区间剩下 n-1 个元素第二次又选到剩余区间的最小值右区间剩下 n-2 个……比较次数是C (n-1) (n-2) ... 1 n(n-1)/2也就是 O(n²)。处理十万个有序元素时这十万次比较量级会从百万级别跳升到十亿级别延迟自然崩掉。更麻烦的是这不是“极端用例”而是任何有序数据都可能触发的常态。2.2 用指示变量把期望比较次数算明白这里引入一套经典的概率分析打法。假设数组排序完成后结果为 z₁ z₂ ... zₙ从小到大排列。定义指示变量 X_{ij}如果 zᵢ 和 zⱼ 在排序过程中被直接比较过则 X_{ij}1否则为 0。总比较次数就是 C Σ X_{ij}所有 ij 的组合求和。为什么“直接比较”这个定义很方便因为在快速排序里任意一对元素最多只会被比较一次。第一次分区之后它们要么被分进同一个子区间继续比较要么从此永远分开。如果它们至今没被比较过后续也不可能再被比较了。关键在于计算被比较的概率。考虑从 zᵢ 到 zⱼ 这段连续区间长度是 j-i1。在这段区间第一次被选为 pivot 之前这 j-i1 个元素一直在同一个递归子问题里。只有两种情况会发生直接比较第一次选的主元恰好是 zᵢ或者恰好是 zⱼ。如果第一次选中的是中间某个元素那么 zᵢ 和 zⱼ 会被划分到以该主元为界的两个不同子区间从此再也没有机会比较。主元选择是均匀随机的所以P(X_{ij}1) 2 / (j-i1)由此期望比较次数为E[C] Σ_{1≤ij≤n} P(X_{ij}1) Σ_{1≤ij≤n} 2/(j-i1)令 d j-i这个式子里 d 从 1 到 n-1每组 d 对应 n-d 对元素。于是E[C] 2 Σ_{d1}^{n-1} (n-d)/(d1) ≤ 2n Σ_{d1}^{n-1} 1/(d1) O(n log n)这是一个非常漂亮的结论无论输入数据是什么顺序期望比较次数都压在 O(n log n)。注意它没有说“每一次运行都一定是 O(n log n)”而是说如果我们重复跑很多次平均来看就是 O(n log n)运气极端差导致退化的概率极其低而且可以通过调整随机化策略进一步压低。2.3 工程实现里的随机主元细节理论归理论工程上写随机化快排时还有几个容易踩的细节。一是随机主元的选取成本。每次分区都调用一次随机数生成对于动辄上亿元素的排序任务这会引入额外的开销。常见的折中方案是先对整个数组做一次洗牌再跑确定性快排或者只在外层递归层面随机化。洗牌的开销也是 O(n)整体复杂度不增加但实现更简单而且随机性提前注入完毕后面递归过程无需再调用随机数生成器。二是随机数生成器的范围要严谨。生成一个 [left, right] 区间的随机下标注意边界不能越界。用random.randint(left, right)这类 API 时要清楚它是闭区间还是开区间很多线上 bug 就出在 left1 还是 left 的边界判断上。三是递归深度问题。随机化快排的最坏递归深度在极端情况下仍然可能达到 O(n)但概率极低。在一些对栈深度敏感的嵌入式环境或受限运行时里我习惯在递归层数超过某个阈值时切换为堆排序作为兜底策略。业界很多优秀排序库就是这么干的比如那种“快排 堆排兜底 插入排序收尾”的组合设计。3. 蓄水池抽样数据流里的均匀抽样如果说随机化快排是“用随机换效率”那蓄水池抽样就是“用随机换内存”。3.1 问题边界与直觉先描述问题一个长度未知的数据流可能非常大甚至无穷无尽要求只能遍历一次从中抽取 k 个元素且保证抽出来的 k 个元素是均匀随机的。换句话说数据流走到第 N 个元素时任意一个已经见过的元素被选入最终样本的概率都必须是 k/N。朴素做法把所有数据全部存下来再抽内存 O(N)数据量大时直接不可行。蓄水池抽样只需要 O(k) 的内存就能在流式环境下完成均匀抽样而且实现逻辑极短。算法描述如下先把前 k 个元素全部放入“蓄水池”一个长度为 k 的数组。从第 i 个元素开始i k生成一个 [0, i) 的随机整数 r如果 r k则用当前元素替换池中下标为 r 的元素否则跳过当前元素。看起来非常反直觉——一个新的元素以 k/i 的概率进池同时又随机挤掉池里一个老元素。为什么这样能做到均匀3.2 归纳法证明我建议所有读到这里的朋友先自己推一遍这是个特别好的概率论练习。证明用归纳法维持一个不变量处理完前 i 个元素后前 i 个元素中任意一个仍然留在池子里的概率都是 k/i。当 i k 时前 k 个元素都被直接放入池中概率 1 k/k基例成立。假设处理完前 i-1 个元素时前 i-1 个元素中任意一个留在池中的概率是 k/(i-1)。现在处理第 i 个元素。对于一个此前已经在池中的元素 e它在处理第 i 个元素后仍然在池中的概率为它在 i-1 时刻仍在池中概率 k/(i-1)且在第 i 个元素被选中进入池时没有被替换掉。第 i 个元素进入池中的概率是 k/i进入后随机占一个下标占中 e 的具体下标的概率是 1/k。因此 e 被替换的概率是 (k/i) × (1/k) 1/i。保留概率为(k/(i-1)) × (1 - 1/i) (k/(i-1)) × ((i-1)/i) k/i至于第 i 个新元素它进入池中的概率本来就被设计为 k/i。所以处理完 i 个元素后所有元素留在池中的概率都是 k/i。当数据流走完时每个元素被选入样本的概率为 k/N满足均匀性要求。这段证明的巧妙之处在于它不要求你知道 N 是多少也不要求中途改变策略一个简单的“持续替换”就能让所有历史元素维持相同的入选概率。在线算法能做到这一点确实让人有种“设计得很优雅”的感慨。3.3 工程示例与扩展用 Python 实现只需要十几行import random def reservoir_sample(stream, k): reservoir [] for i, item in enumerate(stream): if i k: reservoir.append(item) else: r random.randint(0, i) if r k: reservoir[r] item return reservoir这里random.randint(0, i)生成闭区间 [0, i] 的整数配合条件r k刚好模拟了“以 k/(i1) 概率替换”的行为注意下标细节即可。在实际工作中我遇到过两种衍生需求值得展开。一是加权蓄水池抽样。数据流里的每个元素权重不同比如日志里有些来源出现频率高有些低希望样本比例按权重而非元素个数来。朴素做法是把每个元素复制成权重份再抽但权重可能很大复制不现实。业界常用“指数跳跃”变体生成随机指数分布变量来决定每个元素应该“占据”多少虚构位置这样无需展开权重数组也能得到加权均匀样本。这块内容稍微有些深很多网上的实现其实都没考虑权重一致性需要格外谨慎。二是分布式环境下的抽样合并。多台机器各自处理一部分数据流每台生成局部样本之后如果想合并成全局均匀样本不能简单拼接。一种可行方案是每个元素进入全局候选的阈值取决于全局唯一哈希值比如对每个元素生成 [0,1) 随机数保留前 k 小的各路候选收集后归并排序取前 k 个。这样所有机器可以在不通信的情况下产出可合并的样本这也是很多日志采样系统的底层思路。4. 概率结构的启发布隆过滤器的误报控制说到随机化算法在工程系统里最广泛的渗透我觉得不得不提概率数据结构。布隆过滤器虽然不是严格意义上的“随机化算法”——它的哈希函数往往是确定性的——但它把“容忍小概率误差以换取空间和时间”的思路用到了极致和蒙特卡洛范式在哲学上一脉相承。4.1 位数组与哈希函数的组合布隆过滤器的核心结构是一个长度为 m 位的数组全部初始化为 0配 k 个相互独立的哈希函数。插入一个元素时用 k 个哈希函数分别算出 k 个位置全部置 1。查询一个元素是否存在时检查这 k 个位置是否全部为 1如果有任一位置为 0则元素一定不在集合中如果全部为 1则元素可能在集合中也可能误报实际上不存在但位被其他元素置了 1。所以布隆过滤器有个鲜明的特性它没有假阴性只有假阳性。不存在的情况绝不会被漏判存在的情况绝不会被判成不存在但“不存在但被误判为存在”是可能的。这个不对称性让它在很多业务里变得非常实用。比方说做缓存穿透防护请求来的时候先问布隆过滤器一个 key 如果过滤器说“一定不存在”那就直接返回空根本不必去查慢存储。只有过滤器说“可能存在”时才放行到真实存储。由于不存在假阴性布隆过滤器不会漏掉任何真实存在的 key最多是多放行几个本不存在的请求这些请求会被真实存储挡住不会造成错误返回。4.2 误报率公式与参数选择误报率是布隆过滤器最核心的指标。推导并不复杂值得自己算一遍。一个元素经过一个哈希函数后某个特定比特位被置 1 的概率是 1/m不被置 1 的概率是 1 - 1/m。插入 n 个元素、每个元素使用 k 个独立的哈希函数后这个比特位仍然为 0 的概率近似为(1 - 1/m)^(kn) ≈ e^(-kn/m)查询一个不在集合中的元素时它对应的 k 个位置全为 1 的概率就是P(误报) (1 - e^(-kn/m))^k这个公式直接告诉我们两件事误报率随 m/n每个元素占用的比特数增大而下降误报率随 k 的变大不是单调变化的——哈希函数太少碰撞多太多位数组被快速填满。存在一个最优 k 值k ≈ (m/n) × ln 2此时 e^(-kn/m) 1/2误报率降到最低约为 (1/2)^k。我常用这张表来做参数粗选m/n每元素比特数最优哈希函数数 k最低误报率4约 3约 14.7%8约 6约 2.1%16约 11约 0.08%32约 22约 1e-7工程上我一般从 m/n 8 起步也就是每个元素大概 1 字节的位空间误报约 2%对很多过滤场景足够对准确率要求更高的直接上 16 甚至 32。4.3 业务里的用量估算和重建实际选参数时还要考虑集合大小 n 的预估。如果 n 估小了位数组实际塞进更多元素误报率会显著上升估大了空间浪费。有个经验方法先拍一个 n 的上限然后决定能接受的误报率上限反推 m 和 k。要注意的是哈希函数的选择。很多实现直接拿两个基础哈希值做线性组合来模拟多个哈希函数比如 h_i(x) h1(x) i * h2(x)这种方案在工程上广泛使用性能高很多但要注意 h1、h2 的取值空间和最终取模要尽量均匀否则某些 i 组合会产生强烈相关性影响误报率。另一个经常被忽略的设计点是“能不能删除”。标准布隆过滤器不能删除元素因为无法区分某个位到底是被哪个元素置 1 的。如果业务需要支持删除就得换成计数布隆过滤器用计数器数组代替位数组删除时做计数器减一。代价是空间膨胀好几倍还要防止计数器溢出。我自己的经验是大多数只需要“去重判负”的场景标准布隆过滤器就够了需要完整增删的场景不如考虑布谷鸟过滤器或 Count-Min Sketch 这类更复杂的结构别一上来就套布隆过滤器。5. 工程里的随机化“暗坑”种子、复现与测试随机化算法在纸面上非常优雅但接入真实系统时那些“概率分析里不会写”的工程细节往往才是决定成败的部分。我在多个项目里踩过坑这里整理成几条实战经验。5.1 随机数源伪随机与真随机的权衡先说随机数源。算法设计时我们假设有完美的独立均匀随机源但真实世界的随机数都是生成的而且大多数是伪随机数——用一个确定性序列模拟随机性。绝大多数场景下质量合格的伪随机数生成器如很多现代语言标准库里的实现完全够用因为算法的概率分析依赖的是“均匀性”和“独立性”而不是“不可预测性”。只有两种情况需要考虑更高级的随机源一是安全相关场景比如生成密钥、令牌或抽奖防作弊此时不仅要均匀还要防预测应该从系统熵源取数二是某些老旧的、质量很差的随机数实现比如早期某些平台的标准库随机数存在明显的低位周期问题直接用于抽样可能导致结果分布不均匀。如果拿不准就做一次简单统计检验生成几万个随机数分桶统计频次看看每个桶的波动是否符合预期。5.2 可复现性种子记录与重放随机化算法带来的一个非常实际的工程麻烦是同样的输入两次运行可能输出不同结果。这在开发调试时尤其头疼——一个 bug 可能在一次运行中复现、下一次运行消失。我的做法是在所有需要随机化的入口处支持显式指定随机种子seed。上线时种子从高熵源取得测试和 debug 时固定一个种子让行为完全可复现。具体来说抽样式任务比如日志抽样、AB 实验分配在任务配置里记录“本次使用的种子”对账、审计类场景把种子作为元数据写入结果方便事后重放验证单元测试里不要用time()或random全局默认种子固定一个常量种子再跑确保 CI 回归稳定。这样既能保留随机化带来的抗对抗输入能力又保留了确定性的可调试性。种子机制是可复现随机化的基础和底线。5.3 测试随机化代码的正确打开方式随机化算法的测试方法和确定性算法完全不同。如果你写了一个随机化快排普通单元测试断言“排序结果正确”没问题但它不会告诉你随机化是否真的均匀也不会暴露“某一种随机序列会让算法退化”的边界问题。我一般分三层做测试第一层正确性测试。固定种子跑各种输入全升序、全降序、大量重复、空数组、单元素断言结果绝对正确。这一层不关心随机性只关心“结果不能错”。第二层统计性质测试。对蓄水池抽样这类算法跑很多次统计每个元素被选中的频率做卡方检验或简单的比例偏差检查。比如从 1 到 10 的流中抽 1 个元素跑一万次检查每个数字被抽中的次数是否都在 1000 上下。偏差超过几个百分点说明随机源或算法实现有问题。第三层压力与对抗测试。对随机化快排构造能触发确定性版本最坏情况的输入有序数组及其各种变形反复跑很多遍确认没有出现 O(n²) 级退化。这个测试的核心思路是坏输入或许存在但必须证明它无法稳定触发坏情况。有一点务必要提醒对蒙特卡洛类算法单次运行断言结果“正确”是毫无意义的因为结果可能以一定概率错误。正确的测试姿势是观测长时间、多轮次后的错误率是否与理论一致。比如测素性测试就构造一批已知合数重复跑几百次统计误判次数确认比例在理论范围内。一次两次误判不是 bug错误率显著高于理论值那才是 bug。6. 我在实际项目中应用随机化算法的几点体会这篇博文几乎写成了一个小型专题但如果你只带走一样东西我希望是随机化不是你逃避确定性的借口而是你对抗那些“刻意设计的坏输入”和“高昂的最坏代价”时概率分析能帮你算得清清楚楚的工程武器。就我的经验入门阶段最值得先练两个手写实现和两个证明手写随机化快排并推导它的期望比较次数手写蓄水池抽样并证明它的均匀性。这两个基础题吃透之后你对随机化的敏感度会明显不一样。之后再碰到像布隆过滤器这类概率结构就能自然联想到背后的误报率公式而不是停留在“大概有用”的层面。我踩过几次坑之后形成了三条铁律式的习惯第一任何随机化算法的入口都要留种子注入接口永远给可复现性留后路第二上线之前必须做统计性质测试只断言单次“结果对”是远远不够的第三不要把蒙特卡洛算法用在结果不可复核、又没有兜底校验的关键交易链路里。遵守这三条随机化算法几乎不会给你惹祸。另外还要说一点随机化算法不是万能的。它能压低最坏情况出现的概率但没法从原理上彻底消灭它。如果你的系统对延迟的“最坏情况”有硬性要求比如实时交易系统里任何一次超时都不可接受那么即使随机化快排的退化概率已经被压到极低你可能还是需要搭配其他机制。理解这一点才能避免把概率分析当成偷懒的借口。
