L7Easy★ 工业基石 (核心高频)Part L · 经典 ML 与统计模拟
蓄水池抽样(Reservoir Sampling:单遍等概率抽取 k 个样本)
大数据流式处理经典,在总数据量未知甚至无限流中,单遍遍历保证每个样本被选中的概率严格恒为 k/N。
⏱️ 时间复杂度:
O(N) 单遍流式扫描💾 空间复杂度:
O(k) 严格常驻内存🎯 免登录实战自测闭环(先做再看答案)
按「机制回忆 → 关键行填空 → 边界反例 → 追问与错题记录」顺序自测,进度自动保存在本地。
Step 1 · 机制口述与数值稳定性自检
Step 2 · 核心代码关键行补全
import numpy as np
def reservoir_sample_stream(stream, k: int) -> list:
"""
参数:
stream: 可迭代的无限数据流发生器
k: 期望等概率抽取的样本数量
"""
reservoir = []
for i, item in enumerate(stream):
if i < k:
# 前 k 个直接放入蓄水池
reservoir.append(item)
else:
# 依概率 k / (i + 1) 决定是否录取
j =
if j < k:
# 替换掉索引为 j 的旧样本
reservoir[j] = item
return reservoir
Step 3 · 反例与边界断言核对
Step 4 · 面试追问盲答与错题记录
Q1: 如果流式样本本身带有不同的正权重(Weighted Reservoir Sampling),如何保证每个样本被抽取的概率与其权重正比?
💡
实战一句话记忆口诀
前 k 满仓入,后逐以 k 除以 i 抽签,被抽中者任换池中一员,乘积对消概率齐
📐 核心数学公式与机理推导
### 数学归纳法严格等概率证明
面对无限网络数据流(总长度 无法预先获知且内存装不下):
1. 将前 个元素直接填入容量为 的蓄水池;
2. 对于后续到来的第 个元素():
- 以 的概率决定是否收录该元素;
- 若决定收录,在蓄水池已有的 个元素中随机挑一个将其替换淘汰。
归纳法证明:
对于任意第 个元素,它进入蓄水池的概率为 。
在后续每个时间步 中,蓄水池中某个特定位置被新元素替换淘汰的概率为 ,因此幸存概率为 。
累乘历史所有幸存概率:
所有中间项分子分母精准对消,证明无论流有多长,每个样本最终留存的概率严格等于 !
面对无限网络数据流(总长度 无法预先获知且内存装不下):
1. 将前 个元素直接填入容量为 的蓄水池;
2. 对于后续到来的第 个元素():
- 以 的概率决定是否收录该元素;
- 若决定收录,在蓄水池已有的 个元素中随机挑一个将其替换淘汰。
归纳法证明:
对于任意第 个元素,它进入蓄水池的概率为 。
在后续每个时间步 中,蓄水池中某个特定位置被新元素替换淘汰的概率为 ,因此幸存概率为 。
累乘历史所有幸存概率:
所有中间项分子分母精准对消,证明无论流有多长,每个样本最终留存的概率严格等于 !
🔄 张量维度与形状流转说明
流式输入第 i 个元素 -> 随机整数 j 在 [0, i] -> 若 j < k 则 reservoir[j] = item
🛡️ 数值稳定性自检与边界要点
- 生成随机整数的上限必须是 i + 1(即范围为 [0, i]),保证命中概率精确为 k / (i + 1)
- 内存占用极其恒定,永远只驻留 k 个元素
💻 完整参考代码实现
import numpy as np
def reservoir_sample_stream(stream, k: int) -> list:
"""
参数:
stream: 可迭代的无限数据流发生器
k: 期望等概率抽取的样本数量
"""
reservoir = []
for i, item in enumerate(stream):
if i < k:
# 前 k 个直接放入蓄水池
reservoir.append(item)
else:
# 依概率 k / (i + 1) 决定是否录取
j = np.random.randint(0, i + 1)
if j < k:
# 替换掉索引为 j 的旧样本
reservoir[j] = item
return reservoir
🧪 本地测试与正确性断言
可直接复制到本地 Python / Jupyter 验证:
import numpy as np
# 模拟 10000 个流数据抽取 5 个样本
stream = list(range(10000))
sample = reservoir_sample_stream(stream, k=5)
assert len(sample) == 5
assert len(set(sample)) == 5, "样本不应有重复"
print("✓ 蓄水池抽样算法自测通过")🎯 核心工程追问与标准应答
Q1:如果流式样本本身带有不同的正权重(Weighted Reservoir Sampling),如何保证每个样本被抽取的概率与其权重正比?
使用 Efraimidis-Spirakis 的 A-Res 算法:为每个到来的样本计算一个加权随机键值 (其中 ),在内存中维护一个容量为 的最小堆,保留全局键值最大的前 个元素,严格保证采样概率与其权重成正比。
⚡
想检验本题的肌肉记忆?进入 3 阶闪卡主动回忆盲测
隐藏答案遮罩,自测:审题锚点 ➔ 数理公式机理 ➔ 工业标杆代码与连环追问。3 分钟攻破认知盲区!