1229 字
6 分钟
随机算法：洗牌、蓄水池抽样与蒙特卡洛
概述
随机算法（Randomized Algorithms） 利用随机数做选择、抽样或近似估计。它们常用于打乱顺序、从数据流中均匀抽样、按权重分配流量，以及用随机采样估算复杂结果。
前置知识
- 概率基础：理解均匀分布和加权概率
- 前缀和 / 二分：用于高效加权随机选择
- 哈希函数：用于稳定分流，而不是每次完全随机
问题定义
在不确定性参与的场景中，设计满足概率要求的算法，并控制时间、空间和稳定性。
| 要素 | 说明 |
|---|---|
| 输入 | 数组、数据流、权重表或采样次数 |
| 输出 | 随机排列、随机样本、加权结果或近似值 |
| 核心要求 | 概率正确、复杂度可控、必要时可复现 |
| 典型算法 | Fisher-Yates、蓄水池抽样、加权随机、蒙特卡洛 |
核心原理：分步图解
Fisher-Yates 洗牌从后往前固定位置，每次在 [0, i] 中等概率选一个元素交换：
graph LR
A[待洗牌数组] --> B[从最后一位开始]
B --> C[随机选择 0..i]
C --> D[交换到位置 i]
D --> E[i 左移]
E --> C因为第 i 个位置从剩余 i + 1 个元素中等概率选择，所以每个排列出现概率相同。
算法精细步骤
算法：FisherYatesShuffle(arr)输入：数组 arr输出：原地打乱后的数组
1. for i from arr.length - 1 downto 1:2. j ← random integer in [0, i]3. swap arr[i] and arr[j]4. return arr复杂度分析：
| 算法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| Fisher-Yates | O(n) | O(1) | 均匀随机排列 |
| 蓄水池抽样 | O(n) | O(k) | 未知长度数据流抽样 |
| 加权随机线性版 | O(n) | O(1) | 少量选择 |
| 前缀和 + 二分 | O(log n) / 次 | O(n) | 多次加权选择 |
| 蒙特卡洛 | O(samples) | O(1) | 近似估计 |
TypeScript 实现
1. Fisher-Yates 洗牌
function shuffle<T>(arr: T[]): T[] { for (let i = arr.length - 1; i > 0; i--) { const j = Math.floor(Math.random() * (i + 1)); [arr[i], arr[j]] = [arr[j], arr[i]]; }
return arr;}2. 蓄水池抽样
function reservoirSampling<T>(stream: T[], k: number): T[] { const reservoir: T[] = [];
for (let i = 0; i < stream.length; i++) { if (i < k) { reservoir.push(stream[i]); } else { const j = Math.floor(Math.random() * (i + 1)); if (j < k) reservoir[j] = stream[i]; } }
return reservoir;}3. 加权随机选择
interface WeightedItem<T> { value: T; weight: number;}
function weightedRandom<T>(items: WeightedItem<T>[]): T { const total = items.reduce((sum, item) => sum + item.weight, 0); let random = Math.random() * total;
for (const item of items) { random -= item.weight; if (random <= 0) return item.value; }
return items[items.length - 1].value;}4. 前缀和 + 二分优化
class WeightedPicker<T> { private values: T[]; private prefix: number[] = []; private total = 0;
constructor(items: WeightedItem<T>[]) { this.values = items.map(item => item.value);
for (const item of items) { this.total += item.weight; this.prefix.push(this.total); } }
pick(): T { const target = Math.random() * this.total; let left = 0; let right = this.prefix.length - 1;
while (left < right) { const mid = left + Math.floor((right - left) / 2); if (this.prefix[mid] < target) left = mid + 1; else right = mid; }
return this.values[left]; }}5. 蒙特卡洛估算 π
function estimatePi(samples = 1_000_000): number { let inside = 0;
for (let i = 0; i < samples; i++) { const x = Math.random(); const y = Math.random(); if (x * x + y * y <= 1) inside++; }
return (inside / samples) * 4;}6. 稳定 A/B 分流
class ABTesting { private variants: string[]; private weights: number[];
constructor(config: Record<string, number>) { this.variants = Object.keys(config); this.weights = Object.values(config); }
assign(userId: string): string { const total = this.weights.reduce((sum, weight) => sum + weight, 0); const bucket = this.hashCode(userId) % total; let current = 0;
for (let i = 0; i < this.variants.length; i++) { current += this.weights[i]; if (bucket < current) return this.variants[i]; }
return this.variants[this.variants.length - 1]; }
private hashCode(str: string): number { let hash = 0; for (let i = 0; i < str.length; i++) { hash = ((hash << 5) - hash + str.charCodeAt(i)) | 0; } return Math.abs(hash); }}工程优化：随机性、安全性与可复现
| 场景 | 推荐做法 | 原因 |
|---|---|---|
| 普通 UI 随机 | Math.random() | 简单够用 |
| 安全敏感随机 | crypto.getRandomValues() | Math.random() 不适合安全用途 |
| A/B 测试 | 用户 ID 哈希 | 保证同一用户稳定分组 |
| 测试随机算法 | 注入随机数生成器 | 便于复现和单元测试 |
| 多次加权选择 | 前缀和 + 二分 | 预处理后单次 O(log n) |
随机算法的正确性通常是概率意义上的，不应只用单次结果判断实现是否正确。
应用与局限
典型应用
- 列表洗牌、随机播放、抽奖
- 日志流、数据流抽样
- A/B 测试和灰度分流
- 蒙特卡洛估计、随机化 QuickSelect
局限性
| 局限 | 说明 |
|---|---|
| 结果不稳定 | 需要可复现时必须控制随机源 |
| 概率验证困难 | 需要统计测试而不是单个样例 |
| 安全要求不同 | 业务随机和密码学随机不能混用 |
总结
graph LR
A[明确概率目标] --> B[选择随机模型]
B --> C[实现抽样或分流]
C --> D[验证分布]
D --> E[处理可复现和安全要求]核心要点：
- Fisher-Yates 是均匀洗牌的标准算法。
- 蓄水池抽样适合未知长度的数据流。
- 多次加权选择可用前缀和和二分优化。
- 安全场景不要使用
Math.random()。
随机算法：洗牌、蓄水池抽样与蒙特卡洛
https://www.hehonglei.cn/technology/randomized-algorithms/