文档章节

[Algorithm] Reservoir Sampling

o
 osc_n6euf5h6
发布于 2019/03/20 03:22
字数 268
阅读 11
收藏 0

钉钉、微博极速扩容黑科技,点击观看阿里云弹性计算年度发布会!>>>

Given a stream of elements too large to store in memory, pick a random element from the stream with uniform probability.

 

To solve the problem which n size is unknown, Reservior Sampling is a perfect algorithm to use:

Reservoir sampling algorithm can be used for randomly choosing a sample from a stream of n items, where n is unknow.

Here we still need to prove that 

Consider the (i)th item, with its compatibility probability of 1/i. The probability I will be choose the i at the time n > i can be demonstrated by a simple formula

i/i: Probability the ith item will be selected;

(1 - i/i+1): Probability the i+1th item will NOT be selected;

(1 - i/i+2): Probability the i+2th item will NOT be selected;

(1 - 1 / n): Probability the nth item will NOT be selected;

In the end, the probability of ith item will be selected at given n, which n > i is 1/n.

 

Let’s attempt to solve using loop invariants. On the ith iteration of our loop to pick a random element, let’s assume we already picked an element uniformly from [0, i - 1]. In order to maintain the loop invariant, we would need to pick the ith element as the new random element at 1 / (i + 1) chance. For the base case where i = 0, let’s say the random element is the first one. 

function Reservoir_Sampling (ary) {
  let selected;
  const size = ary.length;
  
  for (let i = 0; i < size; i++) {
    if (Math.floor(Math.random() * size) === 1) {
      selected = ary[i];
      break;
    }
  }
  
  return selected;
}

 

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
蓄水池算法

最近有个需求,需要从不固定大小的数据集中取固定数量的数据作为样本,有个同学提到了蓄水池算法,于是了解了一下。 蓄水池算法,本身是为了解决海量数据的随机抽样问题,在算法领域应用还是...

osc_5aj0jo70
2018/01/27
1
0
算法——水塘抽样 reservoirSample

---title: RangePartitioner实现算法reservoirSampleAndCountsubtitle: 水塘抽样算法实现description: sparkCore算法之reservoirkeywords: [spark,reservoir,水塘抽样]author: liyzdate: 20......

freeli
2018/12/12
69
0
蓄水池抽样(Reservoir sampling)

题目要求 从个元素中随机抽取个元素,但的个数无法事先确定。在实际应用中,往往会遇到很大数据流的情况。因此,我们无法先保存整个数据流然后再从中选取,而是期望有一种将数据流遍历一遍就...

go4it
2016/10/22
83
0
Reservoir Sampling - 蓄水池抽样

转载自:http://www.cnblogs.com/HappyAngel/archive/2011/02/07/1949762.html   问题起源于编程珠玑Column 12中的题目10,其描述如下:   How could you select one of n objects at ra......

苗永超
2014/10/16
28
1
蓄水池抽样算法

为分析用户行为,系统常需存储用户的一些query,但因query非常多,故系统不能全存,设系统每天只存m个query,现设计一个算法,对用户请求的query进行随机选择m个,请给一个方案,使得每个que...

兔之
2015/01/15
195
0

没有更多内容

加载失败,请刷新页面

加载更多

【运维探讨】如何实现更加简单、高效、安全的灾备切换管理?

建设了容灾系统,然后呢? 出于业务连续性与数据保护等目的,最早是银行等金融机构完成了业务的容灾系统的建设,随后电力等关键能源行业、海关等政务单位、大型互联网公司都着手建设了完备的...

嘉为科技
15分钟前
13
0
Linux系统内核升级

导读:Linux内核隔段时间会整合一些新特性进行更新,并且生产系统中的内核由于版本过低,会出现各种漏洞,需要安全加固,所以linux环境经常会遇到内核升级的情况,下面我们来看看如何升级lin...

追风若水
05/12
0
0
当你开始学C语言的时候。。。

2020 年上半年高阅读量文章精选 本文分享自微信公众号 - 前端先锋(jingchengyideng)。 如有侵权,请联系 support@oschina.cn 删除。 本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一...

前端先锋
07/07
0
0
没想到还能在这看到云开发...

为了让更多开发者及时掌握云开发的最新动态,欢迎您在下列技术社区、论坛中选择你常用的平台,关注云开发官方账号,来快速了解云开发更新的产品能力与实战项目等内容(扫码即可进入各平台云开...

小程序云开发
07/09
0
0
💐💐课程通俗易懂让你顺利上手JenkinsPipeline的编写。内容涵盖:pipeline基础语法、声明式脚本式、Sharelibrary共享库、Groovy基础语法、常用Pieplin...

本文分享自微信公众号 - DevOps云学堂(idevopsvip)。 如有侵权,请联系 support@oschina.cn 删除。 本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。...

泽阳DevOps
2019/12/29
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部