蓄水池采样算法

问题描述

采样问题经常会涉及到，简单地，有如下形式：

1.从1000000份调查报告中抽1000份进行统计

2.从一本很厚的电话簿中抽1000人进行姓氏统计

3.从Google搜索"AI"的结果中抽100个进行分析

分析： 问题1我们很容易想到生成1至1000000的随机数，抽取1000个，用算法去重保证采样结果不重复即可。问题2与问题3的性质与问题1不同，由于数据规模N可能十分巨大，没有办法将其一次全部读入内存，所以存储所有数据再遍历一次来获取其规模这一做法不可取。

采样问题最重要的是保证公平，即对于总样本集合中的所有元素来说，每个元素需具有相等的概率被选择。这里，我们需要使用随机数算法。

蓄水池采样算法 Reservoir Sampling

Reservoir Sampling是一系列的随机算法。算法过程：
假设数据序列的规模为 n，需要采样的数量的为 k。
首先构建一个可容纳 k 个元素的数组，将序列的前 k 个元素放入数组中。
然后从第 k+1 个元素开始，以 k/n 的概率来决定该元素是否被替换到数组中（数组中的元素被替换的概率是相同的）。当遍历完所有元素之后，数组中剩下的元素即为所需采取的样本。

证明过程

有如下两种情况：
1 . 对于第i个数(i<=k)。在k步之前，被选中的概率为1。从第k+1个元素开始，这个数被第k+1个元素替换的概率 = （第k+1个元素被选中的概率 * i被选中用于替换的概率), 即(k/(k+1))*(1/k) = 1/(k+1)。也就是说，到第k+1个元素为止，第i个元素被保留下来的概率为1-(1/(k+1)) = k/(k+1)。以此类推，遍历到第k+2个元素，第i个元素被保留的概率为1 - (k/(k+2) * (1/k) ) = (k+1)/(k+2)。那么，遍历完全部n个数，第i个数被保留的概率 = 1 * (k/(k+1)) * ((k+1)/(k+2)) * ((k+2)/(k+3)) ... * ((n-1)/n) = k/n。
2 . 对于第j个数(j>k)，在第j步被选中的概率为k/j。其不被第j+1个元素替换的概率为 1 - (k/(j+1)) * (1/k) = j/(j+1)。 也即遍历完第n个数时，第j个数仍被保留的概率 = 被选中的概率 * 不被替换的概率，有如下表达:
(k/j) * (j/(j+1)) * ((j+1)/(j+2)) * ... * ((n-1)/n) = k/n。
综上所述,对于样本集合中的每个数来说，被保留的概率均为 k/n。

例子：

给定一个单链表，随机选择链表的一个节点，并返回相应的节点值。保证每个节点被选的概率一样。

class Solution {
public:
    /** @param head The linked list's head.
        Note that the head is guaranteed to be not null, so it contains at least one node. */
    ListNode* p = nullptr;
    //int len = 0;
    Solution(ListNode* head) {
        // 此处已保证p不为空
        p = head;

    }

    /** Returns a random node's value. */
    int getRandom() {
        //srand((unsigned)time(NULL));
        int i = 0;
        int ans;
        ListNode* p1 = p;
        while(p1)
        {
            ++i;
            if(rand()%i==0)  // 此处蓄水池的容量为1
                ans = p1->val;
            p1 = p1->next;
        }
        return ans;
    }
};