蓄水池抽样算法(reservoir sampling)

场景：在长度未知的数据流中，等概率地采样一定数量的数据。即，数据量N未知，若要求采样k个数据，采样概率保证 k N frac{k}{N} Nk/span>。

要求：只遍历一遍数据，空间复杂度： O ( N ) O(N) O(N)。

内容提要：算法主要思想、证明、LeetCode真题、Java源码。

文章目录

• 蓄水池抽样算法(reservoir sampling)
• • 证明
  • • K=1时
    • K>1时
  • K>1时，蓄水池抽样算法JAVA完整版
  • k=0时，蓄水池抽样算法JAVA完整版
  • LeetCode原题
  • • [398. 随机数索引](https://leetcode-cn.com/problems/random-pick-index/)
    • [382. 链表随机节点](https://leetcode-cn.com/problems/linked-list-random-node/)
  • 埋个坑：分布式蓄水池抽样算法
  • 埋个坑2：

1、申请一个长度为K的数组A保存抽样，数组A相当于容量为K的蓄水池。
2、保存首先接收到的K个元素
3、当接收到第i个新元素t时，以k/i的概率随机替换A中的元素(即生成[1,i]间随机数j，若j<=k，则以t替换A[j])

证明

K=1时

数据流： x 1 , x 2 , , x i , x i + 1 , , x N 1 , x N x_1, x_2, cdots, x_i, x_{i+1}, cdots, x_{N-1}, x_N x1/span>,x2/span>,/span>,xi/span>,xi+1/span>,/span>,xN/span>1/span>,xN/span>

K=1时，相当于要在N个数据流中选择一个数据，此时假设数据的增长下标为i，i从1开始，当i=1时，随机选择一个数据的概率P为1；当i=2时，P为1/2；当i=3时，P为1/3。并且，不论i等于几，第一个数取到的概率总是 1 i frac{1}{i} i1/span>。当这个过过程结束时，每一个对象都有相同的被选概率 1 n frac{1}{n} n1/span>。

证明：

第 i i i个被选中概率=选择第 i i i个对象的概率 × times ×第 i i i个对象到第 n n n个对象没有被选择的概率

K>1时

数据流： x 1 , x 2 , , x i , x i + 1 , , x N 1 , x N x_1, x_2, cdots, x_i, x_{i+1}, cdots, x_{N-1}, x_N x1/span>,x2/span>,/span>,xi/span>,xi+1/span>,/span>,xN/span>1/span>,xN/span>

蓄水池： x 1 , x 2 , , x i , x i + 1 , , x K 1 , x K x_1, x_2, cdots, x_i, x_{i+1}, cdots, x_{K-1}, x_K x1/span>,x2/span>,/span>,xi/span>,xi+1/span>,/span>,xK/span>1/span>,xK/span>

问题就转化为，保证数据出现在蓄水池中的概率为 K N frac{K}{N} NK/span>。

当K大于1时，要在N个数据流中选择K个数据，保证每一个数据被选择的概率相同： K N frac{K}{N} NK/span>。

• 第一种情况：当N小于K时，取每一个对象的概率都相同，每一个都会被取到，所以为1；

• 第二种情况：当N大于K时，需要分步完成：

  • 第1步，先将蓄水池装满：

  • 第2步，当蓄水池装满之后，我们以第 i i i个对象 x i x_i x

    声明：本站部分文章及图片源自用户投稿，如本站任何资料有侵权请您尽早请联系jinwei@zod.com.cn进行处理,非常感谢！