Java教程

水塘抽样算法(Reservoir Sampling)

本文主要是介绍水塘抽样算法(Reservoir Sampling),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

简介:

水塘抽样是一系列的随机算法,其目的在于从包含n个项目的集合S中选取k个样本,其中n为一很大或未知的数量,尤其适用于不能把所有n个项目都存放到内存的情况。

问题:

以谷歌为例,有一道关于水塘抽样的例题

我有一个长度为N的链表,N的值非常大,我不清楚N的确切值.我怎样能写一个尽可能高效地算法来返回K个完全随机的数

我们从题目可以知道三个条件:

  • 数据流长度N很大且不可知,所以不能一次性存入内存。
  • 时间复杂度为O(N)。
  • 随机选取K个数,每个数被选中的概率为K/N。

如果按照常规解法:

将所有数据全部加载完,然后计算链表长度,然后通过random函数来求取K个随机数,这显然是不行的

因此常规的解决的办法无法使用,这是就需要用到---水塘抽样算法

让我们先从随机取一个值来举例

/* 返回链表中一个随机节点的值 */
int getRandom(ListNode head) {
    Random r = new Random();
    int i = 0, res = 0;
    ListNode p = head;
    // while 循环遍历链表
    while (p != null) {
        // 生成一个 [0, i) 之间的整数
        // 这个整数等于 0 的概率就是 1/i
        if (r.nextInt(++i) == 0) {
            res = p.val;
        }
        p = p.next;
    }
    return res;
}

证明:我们要证明上面的代码正确,只要证明这样取任何一个值的概率是1/n即可

假设总共有 n 个元素,那么对于第 i 个元素,它被选择的概率就是:

第 i 个元素被选择的概率是 1/i,第 i+1 次不被替换的概率是 1-1 / (i+1) ,以此类推,相乘就是第 i 个元素最终被选中的概率,就是 1/n。

当我们要随机取K个值时

算法思路如下

  • 如果接收的数据量小于K,则依次放入水池。
  • 当接收到第i个数据时,且i >= m,在[0, i]范围内取以随机数d,若d的落在[0, m-1]范围内,则用接收到的第i个数据替换水池中的第d个数据。
  • 重复步骤2
/* 返回链表中 k 个随机节点的值 */
int[] getRandom(ListNode head, int k) {
    Random r = new Random();
    int[] res = new int[k];
    ListNode p = head;

    // 前 k 个元素先默认选上
    for (int j = 0; j < k && p != null; j++) {
        res[j] = p.val;
        p = p.next;
    }

    int i = k;
    // while 循环遍历链表
    while (p != null) {
        // 生成一个 [0, i) 之间的整数
        int j = r.nextInt(++i);
        // 这个整数小于 k 的概率就是 k/i
        if (j < k) {
            res[j] = p.val;
        }
        p = p.next;
    }
    return res;
}

对此,相关的数学证明差别不大

因此,我们证得对于所有数的概率都是k/n

总结

水塘抽样算法的时间复杂的为O(n),空间复杂度为O(K),是一种非常巧妙的算法,可以运用在大数据中随机取数上

 

这篇关于水塘抽样算法(Reservoir Sampling)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!