亚线性算法-水库抽样算法

Posted by PowderHan on February 3, 2019 已经被偷看过次啦QAQ

http://www.ytmp3.cn/down/53935.mp3



空间亚线性算法

水库抽样(Reservoir Sampling)算法

问题描述

一组数据,大小未知,要求扫描数据一次,空间复杂度 $O(k)$,扫描到数据的前 $n$ 个数字 $(n>k)$ 时,保存当前已扫描数据的 $k$ 个均匀抽样。

算法过程

$1.$ 申请一个长度为 $k$ 的 $A$ 数组保存抽样数据
$2.$ 先保存下前$k$个接收到的元素
$3.$ 当接收到第 $i$ 个新元素 $t$ 的时候,以 $k/i$ 的概率随机替换 $A$ 中的元素
(即生成 $[1, i]$ 间的随机数,若 $j \le k$,则用 $t$ 替换 $A[j]$)

算法分析

  • 性质一:采样均匀

对于一开始放进去的 $k$ 个元素,它们被选取的概率自然直接是$\frac n k$
对于后面进来的第 $i$ 个元素:
刚来时被选取的概率为: $\frac {k} {i}$
之后第 $i+1$ 个元素过来时它还被保留的概率为: $ (1 - \frac{k}{i+1}*\frac{1}{k})$
所以最后还留在$A$中的概率为:
$\frac{k}{i} * (1 - \frac{k}{i+1} * \frac{1}{k} * \cdots * (1 - \frac{k}{n} * \frac{1}{k})) = \frac{k}{n} $

这样就证明了每个元素被选取的概率都是 $\frac{k}{n}$,即为均匀采样

  • 性质二:空间复杂度为$O(k)$

代码实现

import random

a = []
k = int(input())
for i in range(k):
    a.append(int(input()))

while True:
    x = int(input())
    if x == -1:
        break
    j = random.randint(1, i)
    if j <= k:
        a[j] = x

print(a)

The total number of English words:246
The total number of Chinese words:956
欢迎点击下方的知乎图标关注我的知乎QAQ
毕生梦想-成为知乎大V
蟹蟹~