reservoir sampling

“蓄水池抽样”（reservoir sampling）是一种随机抽样的方法，应用于需要在不知道数据总量的情况下从数据流中抽取指定数量的数据样本的情况。这种方法可以通过不依赖于先前观察到的数据而从无限或非常大的数据流中进行抽样。它的主要思想是在数据流的前n个元素中随机选取一个作为“蓄水池”，然后从第n+1个元素开始，每个元素以1/n的概率替换“蓄水池”中的元素。最后形成的“蓄水池”即为所需的样本。

相关问题

r sampling库

Reservoir Sampling（蓄水池采样）算法是一种用于从一个未知大小的数据集中采样固定大小的样本的算法。其原理是使用一个固定大小的采样池，依次遍历数据集，并以一定的概率选择当前元素进入采样池，保证每个元素被选中的概率相等。

在给定一个采样大小K的情况下，算法首先将前K个元素直接放入采样池。然后，对于第K+1个元素开始，以K/i的概率选择当前元素进入采样池，其中i是当前元素的索引。

下面是一个用Java实现的Reservoir Sampling算法的示例代码：

public class ReservoirSampling {
    private int[] pool; // 所有数据
    private final int N = 100000; // 数据规模
    private Random random = new Random();

    public ReservoirSampling() {
        // 初始化
        pool = new int[N];
        for (int i = 0; i < N; i++) {
            pool[i] = i;
        }
    }

    public int[] sampling(int K) {
        int[] result = new int[K];
        for (int i = 0; i < K; i++) {
            // 前 K 个元素直接放入数组中
            result[i] = pool[i];
        }
        for (int i = K; i < N; i++) {
            // K+1 个元素开始进行概率采样
            int r = random.nextInt(i + 1);
            // 这里其实就是K/i的体现
            if (r < K) {
                result[r] = pool[i];
            }
        }
        return result;
    }
}

实现随机权重抽取多个元素的高效算法

实现随机权重抽取多个元素的高效算法通常涉及到概率分布和数据结构的结合。例如，可以使用“ reservoir sampling” 或 “weighted random sampling” 的变种。这里有一个基于 reservoir sampling 的简化版本：

1. **Reservoir Sampling**：这是一种在线（streaming）算法，适用于动态流数据。假设你有一个无限大的序列，并且每个元素都有一个独立的随机权重。你维护一个固定大小的“样本池”，每次从新来的元素中按照其权重随机选择一个替换池里的某个元素，直到收集到所需的元素数。

def weighted_reservoir_sampling(data, k, weights):
    pool_size = min(k, len(weights))
    reservoir = [None] * pool_size
    for i, (item, weight) in enumerate(zip(data, weights)):
        if i < pool_size:
            reservoir[i] = (item, weight)
        else:
            r = int(random.uniform(0, sum(weights[pool_size:i+1])))
            if r < weights[i]:
                reservoir[r] = (item, weight)
    return reservoir