精华内容
下载资源
问答
  • Java算法海量数据等概率随机抽样-蓄水池算法
    2021-02-05 23:41:36

    Java算法海量数据等概率随机抽样-蓄水池算法。

    随即抽样问题:

    要求从N个元素中随机的抽取k个元素,其中N无法确定。

    是在 《计算机程序设计与艺术》 中看到的这个题目,书中只给出了解法,没给出证明。

    解决方法是叫Reservoir Sampling (蓄水池抽样)

    Init : a reservoir with the size: k

    for i= k+1 to N

    M=random(1, i);

    if( M < k)

    SWAP the Mth value and ith value

    end for

    证明:

    每次都是以 k/i 的概率来选择

    例: k=1000的话, 从1001开始作选择,1001被选中的概率是1000/1001,1002被选中的概率是1000/1002,与我们直觉是相符的。

    接下来证明:

    假设当前是i+1, 按照我们的规定,i+1这个元素被选中的概率是k/i+1,也即第 i+1 这个元素在蓄水池中出现的概率是k/i+1

    此时考虑前i个元素,如果前i个元素出现在蓄水池中的概率都是k/i+1的话,说明我们的算法是没有问题的。

    对这个问题可以用归纳法来证明:k < i <=N

    1.当i=k+1的时候,蓄水池的容量为k,第k+1个元素被选择的概率明显为k/(k+1), 此时前k个元素出现在蓄水池的概率为 k/(k+1), 很明显结论成立。

    2.假设当 j=i 的时候结论成立,此时以 k/i 的概率来选择第i个元素,前i-1个元素出现在蓄水池的概率都为k/i。

    证明当j=i+1的情况:

    即需要证明当以 k/i+1 的概率来选择第i+1个元素的时候,此时任一前i个元素出现在蓄水池的概率都为k/(i+1).

    前i个元素出现在蓄水池的概率有2部分组成, ①在第i+1次选择前得出现在蓄水池中,②得保证第i+1次选择的时候不被替换掉

    ①.由2知道在第i+1次选择前,任一前i个元素出现在蓄水池的概率都为k/i

    ②.考虑被替换的概率:

    首先要被替换得第 i+1 个元素被选中(不然不用替换了)概率为 k/i+1,其次是因为随机替换的池子中k个元素中任意一个,所以不幸被替换的概率是 1/k,故

    前i个元素中任一被替换的概率 = k/(i+1) * 1/k = 1/i+1

    则没有被替换的概率为: 1 – 1/(i+1) = i/i+1

    综合① ②,通过乘法规则

    得到前i个元素出现在蓄水池的概率为 k/i * i/(i+1) = k/i+1

    故证明成立

    更多相关内容
  • 算法实现的功能从一个群体(大小为N的数组)中随机抽取一定数量(M个)的样本即从一个大小为N的int数组中随机抽取M个不重复的元素放到一个新数组中算法的设计思想首先需要准备要被抽样的数组num1和存放抽样结果的数组n.....

    说明

    版权所有,仿冒必究

    转载时请标明出处,尊重他人劳动成果,谢谢

    此算法是我个人研究的,经过测试证明我的算法还是不错的。

    166bc01e132e2de0b09c49a50a44f87c.png

    PS:这里的时间可能有点偏小,实际用时是2秒左右,我没有去研究原因了。算法实现的功能

    从一个群体(大小为N的数组)中随机抽取一定数量(M个)的样本

    从一个大小为N的int数组中随机抽取M个不重复的元素放到一个新数组中算法的设计思想

    首先需要准备要被抽样的数组num1和存放抽样结果的数组num2

    然后在M次循环中每次随机抽取一个数存入num2中

    如果,每次从1到N这N个数中随机抽取一个整数作为被抽取的位置的话,那

    么可能会抽取到重复的数字,因此我这里需要产生的随机数应该是原数组去掉已经被抽取的位置之后的位置,你可能会想到每次抽取一个数,就将这个数从原数组里面去掉,然后再用剩下的元素重新组成数组,但是这样的话效率会很低,我

    的想法是用一个list保存每次抽取的位置,由于每次抽取之后剩余的可抽取的数量都会减1,所以产生随机数的范围应当是N减去已经抽取的次数,这样产生

    展开全文
  • 返回值:返回一个伪随机数,该数的范围是:[0,RAND_MAX)2、srand()定义:void srand(unsigned intseed);返回值:该函数是随机数发生器的初始化函数;如果使用相同的种子给rand用,那么rand()会产生相同的伪随机数。...

    1、rand()

    定义:

    int rand(void);

    返回值:返回一个伪随机数,该数的范围是:[0,RAND_MAX)

    2、srand()

    定义:

    void srand(unsigned intseed);

    返回值:该函数是随机数发生器的初始化函数;如果使用相同的种子给rand用,那么rand()会产生相同的伪随机数。常用的用法如下:

    (1) srand((unsigned)time(&t));(2) srand((unsigned)time(NULL));这两个都是用当前时间去初始化种子;

    (3) srand((int)getpid());使用程序的PID来作种子,那么在这个程序运行时种子固定那个。

    3、实战经验

    (1)使用math.h中的函数floor时报如下错误,经查是没有指定链接库。使用gcc -o randint randint.c -lm即可

    (2)采用下面这个例子,生成随机数,如果个数多了,偶尔会有重复的值

    #include

    #include

    #include

    #define NUMBER_MAX 100

    int main(int argc,char* argv[])

    {

    int num[NUMBER_MAX];

    int i;

    FILE *rand_num_file = fopen("rand_num_file.txt","w+");

    srand((unsigned)time(NULL));

    for( i=0; i<100; i++)

    {

    num[i] = rand()%900 + 100;

    fprintf(rand_num_file,"%d\n",num[i]);

    }

    return 0;

    }

    (3)Makefile的学习刻不容缓,十一之后来了主攻《git权威指南》和《shell编程学习指南》

    (4)按照网上的一种解法,实现randint和bigrand:用rand实现bigrand和randint

    仍然会有重复的数值,那么我们怎么解决这个问题呢?我们要的是100~999之间的任意100个随机数,要求不能重复!

    #include

    #include

    #include

    #include

    #define NUMBER_MAX 100

    int randint(int l, int u);

    int main(int argc,char* argv[])

    {

    int num[NUMBER_MAX];

    int i;

    FILE *rand_num_file = fopen("rand_num_file.txt","w+");

    srand((unsigned)time(NULL));

    for( i=0; i<100; i++)

    {

    //num[i] = rand()%900 + 100;//生成[100,999)之间的随机数

    num[i] = randint(100,1000);

    fprintf(rand_num_file,"%d\n",num[i]);

    }

    return 0;

    }

    //实现randint(l,u),返回[l,u]范围内的一个随机整数

    int randint(int l,int u)

    {

    int temp;

    temp = floor(l + (1.0*rand()/RAND_MAX)*(u - l + 1 ));

    return temp;

    }

    补上:

    今天看到用java语言生成随机数,有这么一个想法,也能满足我们的要求:生成[n,m]之间的k个不重复的随机数。参见:点击打开链接

    展开全文
  • 本章先讲解Java随机数的几种产生方式,然后通过示例...本文主要是针对抽样这一行为进行的,而抽样本身有一个隐含的规则就是不要有重复数据。好了,有了这些说明。你可以先尝试着用一些自己的想法来实现不重复地生成...

    本章先讲解Java随机数的几种产生方式,然后通过示例对其进行演示。

    概述:

    这里你是不是会说,生成随机数有什么难的?不就是直接使用Java封装好了的random就行了么?当然对于一般情况下是OK的,而且本文要说明的这些算法也是基于这个random库函数的。

    本文主要是针对抽样这一行为进行的,而抽样本身有一个隐含的规则就是不要有重复数据。好了,有了这些说明。你可以先尝试着用一些自己的想法来实现不重复地生成随机数。

    算法尝试:

    一些好的算法出现,往往伴随着一些不那么好的算法。但是对于效果不太好的算法,它们普遍有一个共性,方便理解和实现。下面是通过一个循序渐进的方式来作一个简单地说明。

    第一次尝试:朴素随机算法

    这个算法很好理解,就是随机!每一次产生一个随机数,并加入集合。

    ?

    第二次尝试:检查存在性随机算法

    我们知道上面的方法有一个问题,就是可能会有重复数据。于是,我们就想到,在生成一个随机数的时候进行检查一下这个数是不是已经存在了,如果存在了就重新生成。

    ?

    第三次尝试:元素移除随机算法

    上面的算法已经解决了数据重复的问题。不过,有一个很糟糕的问题就是可能我们要花费很长的时间来生成抽样随机数(这个要看脸了。。。。)。

    不过,这里我们有了新想法。那就是在一个集合中去随机一个数,当这个被选中的时候就remove掉,那么下次再随机的时候是不是就不会再随机到这个数了?这样就很好地解决了随机数的重复问题。代码如下:

    ?

    第四次尝试:状态转移随机算法

    在我之前的很多博客中,就有一些是算法中的状态转移过程。而状态的转移也是我最喜欢的算法之一。下面的图-1中标注了随机数的取值范围,序列中的橙色数字是结果中的随机序列。最下方的序列中有一些虚线的箭头,代表了状态的转移。

    图-1 基于状态转移的抽样随机数生成算法

    实现代码:

    ?

    第五次尝试:递归Floyd随机算法

    Floyd算法说到底也是一种状态的转移过程。该算法会要求输入一个List或是array来保存已经确定的随机数。顾名思义,这里我会用到递归的解法。在递归的过程中,我们把第i个随机数的状态转移到了第i-1个随机身上了。代码如下:

    ?

    第六次尝试:迭代Floyd随机算法

    思路与上面的递归Floyd随机算法是相似的,不过,这里我们加入了一个变量来做优化。就不需要再去递归了。代码如下:

    ?

    测试结果:

    图-2 随机数生成算法测试结果

    在上面的测试结果中,我们可以很明显地看出朴素随机算法不仅有重复数据,而且还是最耗时的。所以,在抽样的随机数生成时,避免使用这一算法。而在后几种算法中,状态转移随机算法最佳,迭代Floyd随机算法次之。这个可以根据个人偏爱来做选择。

    展开全文
  • java实现随机抽样

    万次阅读 2011-06-06 12:34:00
    编程实现对数据记录的随机抽样。给定概率p,依概率p对给定的数据集合进行随机抽样。比如说现在在一个数组中存放了10000位同学的身高和体重信息,现在需要你对这100位同学以概率p=0.002进行抽样,随机取出这10000位...
  • 从给定的list中做数据抽样,需要保证采样结果数据的分布平衡。/*** 从min - max之间取出总数为items的随机数* @param min* @param items* @param max* @return*/private static List getRandomId(int min,int items,...
  • 主要介绍了Java编程实现二项分布的采样或抽样实例代码,小编觉得还是挺不错的,具有一定借鉴价值,需要的朋友可以参考下
  • 随机抽样一致性(RANSAC)算法能够有效的剔除特征匹配中的错误匹配点。实际上,RANSAC能够有效拟合存在噪声模型下的拟合函数。实际上,RANSAC算法的核心在于将点划分为“内点”和“外点”。在一组包含“外点”的数据...
  • 这个概念即蓄水池抽样(Reservoir Sampling)。 有了这个概念,我们便有了这样一个解决方案:定义取出的行号为choice,第一次直接以第一行作为取出行 choice ,而后第二次以二分之一概率决定是否用第二行替换 choice...
  • 使其成为列表而不是数组,并使用Collections.shuffle()来混淆它.您可以在shuffling之后从List中构建int [].如果你真的想直接进行洗牌,请搜索“Fisher-Yates Shuffle”.以下是使用List技术的...import java.util.Li...
  • ES中如何实现随机抽样查询

    千次阅读 2021-09-10 15:01:27
    索引中有几千万的数据,现在需要每次查询随机抽样返回10条数据,怎么实现?
  • java随机百分比

    2021-07-16 20:28:46
    I need to generate n percentages (integers between 0 and 100) such that the sum of all n numbers adds up to 100.If I just do nextInt() n times, each time ensuring that the parameter is 100 minus the p...
  • 主要介绍了Java编程实现beta分布的采样或抽样实例,分享了相关代码示例,小编觉得还是挺不错的,具有一定借鉴价值,需要的朋友可以参考下
  • java list随机抽取元素

    2021-04-22 16:39:00
    /***从list中随机抽取元素**@paramlist*@paramn*@returnvoid*@throws*@Title:createRandomList*@Description:TODO*/privatestaticListcreateRandomList(Listlist,intn){//TODOAuto-generatedm...
  • 不就是直接使用Java封装好了的random就行了么?当然对于一般情况下是OK的,而且本文要说明的这些算法也是基于这个random库函数的。本文主要是针对抽样这一行为进行的,而抽样本身有一个隐含的规则就是不要有重复数据...
  • sql写随机抽样总结

    千次阅读 2019-07-26 15:23:52
    一、Oracle取随机数据 1、Oracle访问数据的基本方法: 1)、全表扫描(Full table Scan):执行全表扫描,Oracle读表中的所有记录,考查每一行是否满足WHERE条件。Oracle顺序的读分配给该表的每一个数据块,且每个数据...
  • 前言事情起源于一位网友分享了一个有趣的面试题:生成由六位数字组成的ID,要求随机数字,不排重,不可自增,且数字不重复。ID总数为几十万。初次解答我一开始想到的办法是生成一个足够大的ID池(其实就是需要多少就...
  • 比如有一个高 10 米的蓄水池,我们需要对随机一个 1 米的水层进行抽样,这时候很多人都会想到直接生成一个 (0, 10] 的随机数就可以解决,那么要是把高 10 米的条件去掉呢?这显然就不是一个随机数就能解决的了,这...
  • 可用于生成指定范围的随机端口号 public void checkPort() { int iMin = 26111; int iMax = 26333; // 变量可作入参, 范围大于零才校验 if (iMax - iMin > 0) { int iCnt = iMax - iMin + 1; int iOffset ...
  • 展开全部比如有十个糖果,按照2:3:5的比例分配给三个小e68a84e8a2ad62616964757a686964616f31333363366231孩publicclassluck{publicstaticListcandy=newArrayList();publicstaticListchild1=newArrayList();...
  • java生成随机序列

    2021-02-28 14:42:37
    ​ 4.first() 返回数据集的第一个元素(类似于take(1)) ​ 5.takeSample(withReplacement, num, [seed]) 对于一个数据集进行随机抽样,返回一个包含num个随机抽样元素的数组,withReplacement表示是否有放回...
  • java 加权随机数实现

    2021-03-13 13:33:35
    import java.util.HashMap; import java.util.Map; import java.util.Random; public class Test1 { // String 可以为任意类型 也可以自定义类型 static Map keyChanceMap = new HashMap(); static { // ...
  • java随机采样

    2021-03-06 19:57:23
    ​ 4.first() 返回数据集的第一个元素(类似于take(1)) ​ 5.takeSample(withReplacement, num, [seed]) 对于一个数据集进行随机抽样,返回一个包含num个随机抽样元素的数组,withReplacement表示是否有放回...
  • 本文实例为大家分享了java利用数组随机抽取幸运观众的具体代码,供大家参考,具体内容如下思想:首先将所有观众姓名生成数组,然后获取数组元素的总数量,再在数组元素中随机抽取元素的下标,根据元素的下标得到幸运...
  • public class TestStudent { public static void main(String[] args) { //要求随机抽取三次,不重复 ArrayList stuList = addStu(); showStuList(stuList); getRanStu(stuList); showStuList(stuList); getRanStu...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 5,181
精华内容 2,072
关键字:

随机抽样java

java 订阅