算法篇-Reservoir Sampling 蓄水池抽样

简介

水库抽样是一系列随机算法，用于从 n 个项目的列表中随机选择k个样本，其中n是一个非常大或未知的数字。通常n足够大，以至于列表不适合主内存。例如，Google 和 Facebook 中的搜索查询列表。所以我们得到了一个大的数字数组（或流），我们需要编写一个有效的函数来随机选择k个数字，其中1 <= k <= n。让输入数组为stream[]。

一个简单的解决方案是创建一个最大大小为k的数组存储库[]。一个一个地从stream[0..n-1]中随机选择一个项目。如果选中的项目之前没有被选中，则将其放入水库[]。要检查一个项目是否先前被选中，我们需要在水库[]中搜索该项目。该算法的时间复杂度为O(k^2)。如果k很大，效率可能会低。此外，如果输入是流的形式，这也不是有效的。

思路

它可以在O(n)时间内解决。该解决方案也非常适合流形式的输入。以下是步骤。
1）创建一个数组reservoir[0..k-1]并将stream[]的前k个项目复制到它。
2）现在一个一个地考虑从第（k+1）个项目到第n个项目的所有项目。

• a)生成一个从 0 到i的随机数，其中i是stream[]中当前项目的索引。令生成的随机数为j。
• b)如果j在 0 到k-1的范围内，则用流[i]替换数组 [j]

证明

• 假设当前是第 M+1 个元素, 它被丢弃的概率是 1/(M+1), 留下的概率就是 M/(M+1). 对于已经在集合中的M个元素, 每个以 1/(M+1) 的概率被丢弃, 留下的概率也是 M/(M+1).
• 假设当前是第 M+2 个元素, 它被丢弃的概率是 2/(M+2), 留下的概率是 M/(M+2). 对于前 M+1 个元素, 它们在集合中的概率是 M/(M+1). 这一次, 它们每个被以1/(M+2)的概率被丢弃, 留下的概率就是 M/(M+1) (M+1)/(M+2) = M/(M+2)
• 依次类推, 到接受第N个元素时, 每个元素被抽取的概率就是M/N

实现

public class ReservoirSampling {
    static void selectKItems(int stream[], int n, int k) {
        int i; //流中元素的索引
        //需要返回的k个样本
        int reservoir[] = new int[k];
        //样本小于k直接返回
        for (i = 0; i < k; i++) reservoir[i] = stream[i];
        Random r = new Random();
        // 从第（k+1）个元素迭代到第n个元素
        for (; i < n; i++) {
            // 随机获取[0,i]的一个数
            int j = r.nextInt(i + 1);
            //如果随机选取的索引小于k，然后替换获取的随机数
            if (j < k) reservoir[j] = stream[i];
        }
        System.out.println("Following are k randomly selected items");
        System.out.println(Arrays.toString(reservoir));
    }
    //测试
    public static void main(String[] args) {
        int stream[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
        int n = stream.length;
        int k = 5;
        selectKItems(stream, n, k);
    }
}

案例

给你一个可能含有 重复元素 的整数数组 nums ，请你随机输出给定的目标数字 target 的索引。你可以假设给定的数字一定存在于数组中。

public class Solution {

    int[] nums;
    Random random;

    public Solution(int[] nums) {
        this.nums = nums;
        random = new Random();
    }

    /**
     * 遍历 nums，当我们第 i 次遇到值为 target 的元素时，随机选择区间 [0,i) 内的一个整数，如果其等于 0，则将返回值置为该元素的下标，否则返回值不变。
     * 设 nums 中有 k 个值为 target 的元素，该算法会保证这 k 个元素的下标成为最终返回值的概率均为 1/k
     *
     * 第1次遇到,在[0,1)中获取随机数,其必定为0 0概率=1
     * 第2次遇到,在[0,2)中获取随机数,其必定为0,1 0概率=1/2
     * 第3次遇到,在[0,3)中获取随机数,其必定为0,1,2 0概率=1/3
     * 第k次遇到,在[0,k)中获取随机数,其必定为0,1,2,...k-1 0概率=1/k (关键) 所以最后一次获取的随机数就是1/k
     */
    public int pick(int target) {
        int ans = 0;
        for (int i = 0, cnt = 0; i < nums.length; ++i) {
            if (nums[i] == target) {
                ++cnt; // 第 cnt 次遇到 target
                if (random.nextInt(cnt) == 0) {
                    ans = i;
                }
            }
        }
        return ans;
    }
}

资料

https://www.geeksforgeeks.org/reservoir-sampling/?ref=gcse
https://leetcode-cn.com/problems/random-pick-index