蓄水池样片（Reservoir Sampling)分析

蓄水池抽样（Reservoir Sampling)分析

其目的在于从包含n个项目的集合S中选取k个样本，其中n为一很大或未知的数量，尤其适用于不能把所有n个项目都存放到主内存的情况。应用的场景一般是数据流的情况下，由于数据只能被读取一次，而且数据量很大，并不能全部保存，因此数据量N是无法在抽样开始时确定的，但又要保持随机性。

在高德纳的计算机程序设计艺术中，有如下问题：

“可否在一未知大小的集合中，随机取出一元素？”

idea：选择第一个对象，并使用1/2的概率选择第二个对象，使用1/3的概率选择第三个对象，以此类推。在过程结束时，每个对像被选中的概率都是1/n。

                     

以上问题可扩展为

  “可否在一未知大小的集合中，随机取出k个元素？”

idea：先选中前k个， 从第k+1个元素到最后一个元素为止， 以1/i  (i=k+1, k+2,...,N) 的概率选中第i个元素， 并且随机替换掉一个原先选中的元素， 这样遍历一次得到k个元素， 可以保证完全随机选取。

          

该算法的变种有：

• 给你一个长度为N的链表。N很大，但你不知道N有多大。你的任务是从这N个元素中随机取出k个元素。你只能遍历这个链表一次。你的算法必须保证取出的元素恰好有k个，且它们是完全随机的（出现概率均等）。
• 从一个不知长度的文件中随机抽出k行。
• 从实时的搜索词中随机抽出k个词。