请选择 进入手机版 | 继续访问电脑版

水库抽样

[复制链接]
蝶蝶已蝶已蝶蝶 发表于 2021-1-3 12:07:14 | 显示全部楼层 |阅读模式 打印 上一主题 下一主题
输入:一组数据,其巨细未知
输出:这组数据的K个匀称抽样
要求:

  • 仅扫描数据一次
  • 空间复杂性为O(K)【和抽样巨细有关,和整个数据量无关,不可把所有数据都放在内存里举行抽样】
  • 扫描到数据的前n个数字时(n>K),生存当前已扫描数据的K个匀称抽样
针对此种需求,水库抽样法应运而生
算法步调:

  • 申请一个长度为K的数组A生存抽样
  • 生存首先吸收到的K个元素
  • 当吸收到第 i 个新元素 t 时,以 K / i 的概率随机替换A中的元素(即生成 [  1, i ]间随机数j,若 j ≤ K,则以 t 替换 A[ j ])
算法性质:


  • 该采样是匀称的。
即在任何时候,吸收到的大于K的n个数据,选出来的数都包管是匀称采样。
第 i 个数据吸收到的时候是以 K / i 的概率在A当中,在吸收到第 i + 1的时候,第 i 个数据还能生存在A当中的概率为(1 - (1 / i+1) ),因为在吸收到第 i + 1个数的时候,第 i + 1 个数要以 K/(i +1)的概率随机替换A中的元素,而元素 i 在这一步被选出来替换的概率是1/K,这两个相乘为 1 / ( i+1),便为第 i 个元素被选出的概率,所以(1 - (1 / i+1) )为在第 i+1 个元素吸收到的时候,第 i 个数在数组的概率。以此类推,在第 i+2 个数到来的时候,第 i 个数仍然在数组中的概率为(1 - (1 / i+2) ),当担当到第n个数的时候,第 i 个数生存在数组的概率为(1 - (1 / n) )。只有这些事件都发生了,那么才气在吸收到第 n 个数的时候,第 i 个数还生存在抽样当中,所以其生存在抽样当中的概率为这些事件相乘。



  • 空间复杂性为O(K)
在整个的算法处置处罚当中,我们只需要一个长度为K的数组生存抽样,剩下的盘算概率的啥的空间都是常数的,因此空间复杂度为O(K)

来源:https://blog.csdn.net/weixin_43717681/article/details/112055776
免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则


专注素材教程免费分享
全国免费热线电话

18768367769

周一至周日9:00-23:00

反馈建议

27428564@qq.com 在线QQ咨询

扫描二维码关注我们

Powered by Discuz! X3.4© 2001-2013 Comsenz Inc.( 蜀ICP备2021001884号-1 )