寻求无需留存样本的Reservoir Sampling类流式采样算法

你要的是能从数据流中即时输出选中元素、且输出后不会被覆盖，同时不用留存整个数据流或样本集合的抽样算法，以下是针对不同场景的解决方案：

算法名称 #

• 若已知数据流总长度：使用顺序泊松抽样（Sequential Poisson Sampling），能保证恰好选中k个元素，且每个元素被选中概率均等，选中后可立即输出无需留存。
• 若未知数据流总长度：只能采用**伯努利抽样（Bernoulli Sampling）**的折中方案，每个元素被选中概率固定，选中后即时输出，但最终选中的元素数量是随机的（期望为k）。

问题说明 #

你提供的蓄水池抽样代码之所以不符合要求，是因为它需要通过替换已选中元素来维持样本平衡，这就必须留存样本集合，且已输出的元素可能被后续元素替换，无法满足“选中即输出且不覆盖”的要求。

Python实现 #

场景1：已知数据流总长度n #

import random

def sequential_poisson_sampling(stream, sample_size, total_length):
    selected_num = 0
    for idx, elem in enumerate(stream, start=1):
        # 计算当前元素被选中的概率
        select_prob = (sample_size - selected_num) / (total_length - idx + 1)
        if random.random() < select_prob:
            print(elem)  # 即时输出，无需保存样本
            selected_num += 1
            if selected_num == sample_size:
                break  # 选够数量后停止处理

场景2：未知数据流总长度（折中方案） #

如果完全不知道数据流总长度，且接受最终选中数量的期望为k，每个元素被选中概率均等，可以用这个实现：

import random

def immediate_bernoulli_sampling(stream, expected_sample_num, estimated_total):
    select_prob = expected_sample_num / estimated_total
    for elem in stream:
        if random.random() < select_prob:
            print(elem)  # 即时输出

关键提醒 #

• 蓄水池抽样的核心依赖“替换机制”，这是它能在未知数据流长度下保证样本均匀性的前提，因此必然不符合“即时输出不覆盖”的要求。
• 只有当数据流总长度已知时，才能同时满足“恰好k个样本”、“每个元素被选中概率均等”、“即时输出不覆盖”、“不留存样本集合”这四个条件。未知长度场景下只能做折中。

内容的提问来源于stack exchange，提问作者Stack Overflow