L7Easy★ Core Essential · Industrial BedrockPart L · Classical ML & Statistical Simulation
Reservoir Sampling Algorithm
Fixed-memory streaming Reservoir Sampling keeping every item with exact uniform probability k/N.
⏱️ Time:
O(N) 单遍流式扫描💾 Space:
O(k) 严格常驻内存🎯 Interactive Self-Practice Loop (Attempt Before Peeking)
Practice in 4 steps: recall mechanism, complete core lines, check edge cases, and log mastery locally.
Step 1 · Mechanism Recall & Stability Self-Check
Step 2 · Complete Key Implementation Lines
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 · Verify Boundary Cases & Assertions
Step 4 · Follow-Up Drill & Review Outcome
Q1: How is Reservoir Sampling adapted for positive item weights (Weighted Reservoir Sampling)?
💡
Core Mental Anchor / Mnemonic
Fill first k slots, then accept item i with probability k/(i+1) replacing a random slot.
📐 Mathematical Derivation & Core Formula
### Exact Uniform Sampling Proof over Unbounded Streams
To sample items uniformly from a stream of unknown length :
1. Store the first items in the reservoir;
2. For each subsequent item , keep it with probability , replacing a uniformly chosen slot in the reservoir.
By induction, item enters with probability and survives every step with probability ; the telescoping product equals identically for every item.
To sample items uniformly from a stream of unknown length :
1. Store the first items in the reservoir;
2. For each subsequent item , keep it with probability , replacing a uniformly chosen slot in the reservoir.
By induction, item enters with probability and survives every step with probability ; the telescoping product equals identically for every item.
🔄 Tensor Dimensions & Shape Flow
stream item i -> draw random int j in [0, i] -> if j < k: reservoir[j] = item
🛡️ Numerical Stability & Pitfalls Checklist
- Sample uniform integer j over inclusive
[0, i](randint(0, i)orrandrange(i + 1)) for exact k/(i+1) odds. - Memory footprint remains fixed at O(k) regardless of stream length N.
💻 Reference Code Implementation
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
🧪 Runnable Assertions & Validation
Copy and run directly in 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("✓ 蓄水池抽样算法自测通过")🎯 Core Follow-up Inquiries & Reference Answers
Q1:How is Reservoir Sampling adapted for positive item weights (Weighted Reservoir Sampling)?
Use the Efraimidis-Spirakis A-Res algorithm: assign each arriving item a key with and maintain a min-heap of size keeping the largest keys.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.