L7Easy★ Core Essential · Industrial BedrockPart L · Classical ML & Statistical Simulation

Reservoir Sampling Algorithm

⚡Flashcard Drill➔

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)?
Next: Moving Average (Sliding Window & Exponential) →
💡

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

P(Item i in reservoir at step N)=ki×∏j=i+1N(1−1j)=kNP(\text{Item } i \text{ in reservoir at step } N) = \frac{k}{i} \times \prod_{j=i+1}^N \left(1 - \frac{1}{j}\right) = \frac{k}{N}
### Exact Uniform Sampling Proof over Unbounded Streams
To sample kk items uniformly from a stream of unknown length NN:
1. Store the first kk items in the reservoir;
2. For each subsequent item i>ki > k, keep it with probability k/ik/i, replacing a uniformly chosen slot in the reservoir.
By induction, item ii enters with probability k/ik/i and survives every step j>ij > i with probability 1−kj⋅1k=j−1j1 - \frac{k}{j}\cdot\frac{1}{k} = \frac{j-1}{j}; the telescoping product equals kN\frac{k}{N} 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) or randrange(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 ui1/wiu_i^{1/w_i} with ui∼Uniform(0,1)u_i \sim \mathrm{Uniform}(0, 1) and maintain a min-heap of size kk 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.
🎯 Drill This Card Now➔
← Prev: Welford's Algorithm for Online Mean & VarianceBack to Part L & All 105Next: Moving Average (Sliding Window & Exponential) →