Reservoir Sampling
概念解释
水库抽样在不知道流长度时保持固定容量的均匀随机样本。
核心方法与条件
第 i 个元素以 k/i 概率进入容量 k 的水库，并随机替换已有项。
例题或应用
从无限日志流中维护 1000 条均匀样本。
常见易错点
加权抽样和时间衰减需要不同算法，不能直接套普通水库。
自检
请尝试不用原文解释“Reservoir Sampling”解决什么问题，再设计一个属于“流式与近似算法”的实例，并说明适用条件和判断依据。
水库抽样在不知道流长度时保持固定容量的均匀随机样本。
第 i 个元素以 k/i 概率进入容量 k 的水库，并随机替换已有项。
从无限日志流中维护 1000 条均匀样本。
加权抽样和时间衰减需要不同算法，不能直接套普通水库。
请尝试不用原文解释“Reservoir Sampling”解决什么问题，再设计一个属于“流式与近似算法”的实例，并说明适用条件和判断依据。