蓄水池采样算法
问题描述
采样问题经常会涉及到，简单地，有如下形式：
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;
}
};
查看9道真题和解析
，