云端 Mac 上验收 iOS 蓄水池抽样：可控随机源与穷举验证

在 Windows 上写好日志筛选功能后，需要从数量未知的事件流里随机保留少量记录。把全部记录读进数组再打乱，会让内存随输入增长。在云端 Mac 上，可以先用 Swift 验收蓄水池抽样，再把同一份实现接入 iOS 工程。关键不是观察结果“像不像随机”，而是把选择规则变成可重复检查的契约。

固定抽样单位与容量契约

本文使用 Algorithm R：先保留前 k 项；读到第 t 项时，从零到 t−1 均匀抽取整数 j，只有 j 小于 k 才替换对应槽位。遍历结束后，每个输入位置的入选概率都是 k/n，额外存储为 O(k)，遍历耗时为 O(n)。

这个结论要求每一步抽签在给定历史的条件下仍然均匀。仅仅让随机数落在正确范围，并不足以保证公平。

先约定四个边界：容量不能为负；容量为零时返回空样本且不消费输入；输入少于容量时全部保留；重复值按不同位置分别参与。输出槽位顺序不是随机排列，也不承诺保持原始顺序。

抽样公平不等于每次结果不同。把“连续两次不能相同”写进测试，会把正常随机结果变成偶发故障。

将随机源从选择逻辑中拆开

登录 OSXMesh 云端 Mac 后，在终端执行 xcrun swift --version，确认当前工具链能够运行 Swift。将下面代码保存为 ReservoirCheck.swift。闭包接收排他的上界，使生产随机源与测试脚本共用同一套选择逻辑。

func reservoir<S: Sequence>(
    _ input: S,
    capacity: Int,
    draw: (Int) -> Int
) -> [S.Element] {
    precondition(capacity >= 0)
    guard capacity > 0 else { return [] }

    var sample: [S.Element] = []
    var seen = 0

    for value in input {
        seen += 1
        if sample.count < capacity {
            sample.append(value)
        } else {
            let slot = draw(seen)
            precondition(slot >= 0 && slot < seen)
            if slot < capacity {
                sample[slot] = value
            }
        }
    }
    return sample
}

let empty = reservoir([Int](), capacity: 2) { _ in
    preconditionFailure("Unexpected draw")
}
precondition(empty.isEmpty)

let zero = reservoir([1, 2], capacity: 0) { _ in
    preconditionFailure("Unexpected draw")
}
precondition(zero.isEmpty)

let short = reservoir([1, 2], capacity: 3) { _ in
    preconditionFailure("Unexpected draw")
}
precondition(short == [1, 2])

var counts: [String: Int] = [:]

for first in 0..<3 {
    for second in 0..<4 {
        var script = [first, second].makeIterator()
        var bounds: [Int] = []

        let sample = reservoir(0..<4, capacity: 2) { upper in
            bounds.append(upper)
            guard let next = script.next() else {
                preconditionFailure("Draw script exhausted")
            }
            return next
        }

        precondition(bounds == [3, 4])
        precondition(script.next() == nil)
        precondition(sample.count == 2)
        precondition(Set(sample).count == 2)

        let key = sample.sorted().map { String($0) }
            .joined(separator: ",")
        counts[key, default: 0] += 1
    }
}

let expected = ["0,1", "0,2", "0,3", "1,2", "1,3", "2,3"]
precondition(Set(counts.keys) == Set(expected))
precondition(counts.values.allSatisfy { $0 == 2 })

运行 xcrun swift ReservoirCheck.swift。通过时不输出内容，失败则以非零状态退出。脚本使用前置条件检查，不应以关闭安全检查的优化选项执行。实际应用面对外部容量参数时，应先校验，再调用算法，而不是让非法输入触发进程终止。

穷举十二条路径验证选择规则

四个候选位置取两个，第三项对应三个选择，第四项对应四个选择，因此共有十二条路径。每条路径在上述随机源假设下概率均为十二分之一，六个无序位置组合应各出现两次。

这里检查的是组合分布，而不只是单个位置出现次数。某些错误实现可能让每项边际频率接近一致，却始终遗漏部分组合。

脚本同时核对随机源收到的上界必须为三和四，并检查脚本恰好耗尽。少调用一次、额外调用一次，或者把上界误写成当前槽位数，都会失败。排序只用于生成比较键，不应偷偷改变生产函数的返回契约。

这一规模可以抓住常见的替换条件错误，但不是任意输入规模的数学证明。合并前仍需审查归纳条件，并对其他小规模容量补充穷举用例。

覆盖重复值与流式输入陷阱

重复值测试应使用带唯一序号的记录。例如两个内容相同的事件分别标为位置零和位置一，断言入选位置不重复，不能简单断言样本中的业务值唯一。先去重再抽样，会改变每类事件的权重，也会引入额外存储。

容量为一时，要分别强制替换与强制跳过；容量等于输入长度时，不应调用随机源；容量大于输入长度时，输出长度应等于输入长度。

对只能消费一次的序列，再加一个统计读取次数的迭代器。容量为零时读取次数必须为零，正容量时只遍历一次。不要为了预先取得长度调用 Array(input)，否则虽然选择结果正确，流式内存目标已经失效。

计数器还要求输入项数可以由 Int 表示。无终点事件流应按窗口结束抽样，不能期待这个同步函数自行返回；取消与窗口关闭应由上层控制。

接入工程时保留可复现证据

生产调用可以使用 Int.random(in: 0..<upper) 提供整数，不要用随机整数取模来凑范围，也不要把固定测试脚本带进正式功能。这里的抽样用于一般数据处理，不应直接承担安全抽签职责。

将脚本随仓库提交，在云端 Mac 的构建步骤中先执行，再运行工程测试。一次失败至少保留输入位置、容量、抽签序列和工具链版本；不要为排查而记录真实用户事件正文。

最后把验收分成三层：确定性的边界用例、小规模路径穷举、独立的统计观察。统计观察适合发现随机源接线异常，不宜用过窄的频率阈值阻断每次提交。回归依据应是明确可重放的失败路径，而不是某次抽样恰好不合直觉。

常见问题