蓄水池抽样

常用综合题型

说明

流式处理未知长度的数据并等概率保留一个样本；第 i 项以 1/i 概率替换。

分析

处理第 i 个元素时，以 1/i 的概率替换当前样本。归纳可知，处理完 i 个元素后每个元素仍以 1/i 的概率被保留，因此无需事先知道流长度。

图解推演

前三个值为 10、20、30 时，先保留 10；第二个以 1/2 替换，第三个以 1/3 替换。最终 10 和 20 各以 (1/2)×(2/3)=1/3 留下，30 以 1/3 留下。这个概率论证依赖均匀随机选择；固定种子只用于复现，不能把单次抽样结果当作均匀性的证明。

查看图表代码

适用前提与边界

示例固定随机种子便于复现；实际场景可传入自己的随机源。

示例输入与调用

rng := rand.New(rand.NewSource(7))
	value, ok := Reservoir([]int{10, 20, 30}, rng)
	fmt.Println(value, ok)

运行输出

30 true

完整 Go 示例

package main

import (
	"fmt"
	"math/rand"
)

func Reservoir(stream []int, rng *rand.Rand) (int, bool) {
	sample := 0
	for i, x := range stream {
		if rng.Intn(i+1) == 0 {
			sample = x
		}
	}
	return sample, len(stream) > 0
}

func main() {
	rng := rand.New(rand.NewSource(7))
	value, ok := Reservoir([]int{10, 20, 30}, rng)
	fmt.Println(value, ok)
}