【高级技巧】蓄水池抽样：总量未知时的等概率抽取

底层原理

从持续增长的报名名单里等概率抽出 3 人获得祖玛教主远征资格：先收全名单再抽，名单要多大内存有多大。蓄水池抽样一遍流过：前 k 个直接入池，第 i 个以 k/i 的概率随机替换池中一员；流结束时每个元素入选概率都恰为 k/总数——严格等概率，内存只有常驻的 k 个名额。正确性由连乘保证：第 i 个入选且幸存到末尾的概率是 (k/i) 乘后续各轮的幸存率，正好收敛到 k/n。

高级封装

一遍流过的等概率抽取。示例代码如下：

local function reservoir(names, k)
    local pool = {}
    for i, name in ipairs(names) do
        if i <= k then
            pool[i] = name
        else
            local j = math.random(1, i)
            if j <= k then
                pool[j] = name
            end
        end
    end
    return pool
end

远征资格抽取接线。示例代码如下：

local winners = reservoir(signUpList, 3)
for _, name in ipairs(winners) do
    local actor = getplayerbyname(name)
    if actor then
        sendmsg(actor, 1, "获得祖玛教主远征资格。")
    end
end

性能对比

3000 人名单抽 3 人：先全存再洗牌要 3000 个槽位约 600KB，蓄水池常驻只有 3 个名额（省 99.9% 内存），两者交换次数同为 3000 次量级。名单到 10 万级差距拉大：洗牌法要整表约 20MB 常驻，蓄水池仍只要 3 个名额；一遍流过还意味着名单可以边生成边抽，不需要先存全表。

适用边界

三个不适用场景：一是名单已完整在手且要反复抽，洗牌一次按序取更简单；二是要求"历史中奖者不再入选"，要在入口先过滤，蓄水池本身不认识历史；三是按权重的不等概率抽取（高战多抽）不是标准蓄水池的领域，需要换加权算法。