Loading [MathJax]/jax/output/CommonHTML/config.js
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
社区首页 >问答首页 >在一定范围内生成无偏随机整数的最优算法是什么?

在一定范围内生成无偏随机整数的最优算法是什么?
EN

Stack Overflow用户
提问于 2012-08-01 04:05:04
回答 7查看 7.4K关注 0票数 16

在这个StackOverflow问题中:

从范围生成随机整数

所接受的答案表明,在给定的minmax之间生成随机整数的公式如下,其中包括minmax

代码语言:javascript
运行
AI代码解释
复制
output = min + (rand() % (int)(max - min + 1))

但它也说

这还是有点偏低的数字..。它也有可能扩大它,以便它消除偏见。

但这并不能解释为什么它偏向较低的数字,或如何消除偏见。因此,问题是:这是在(有符号)范围内生成随机整数的最优方法,而不依赖于任何花哨的rand()函数,如果是最优的话,如何消除偏差?

编辑:

我刚刚测试了@ while-loop提出的浮点外推算法:

代码语言:javascript
运行
AI代码解释
复制
static const double s_invRandMax = 1.0/((double)RAND_MAX + 1.0);
return min + (int)(((double)(max + 1 - min))*rand()*s_invRandMax);

为了看有多少均匀的“球”正在“落入”并分布在许多“桶”中,一种是浮点外推的测试,另一种是while-loop算法的测试。但是结果却是不同的,取决于“球”(和“桶”)的数量,所以我很难轻易地选出一个获胜者。工作代码可以在这一页找到。例如,对于10个桶和100个球,浮点外推法与理想概率的最大偏差小于while-loop算法(分别为0.04和0.05 ),而对于1000个球,while-loop算法的最大偏差较小(0.024和0.011),而对于10000个球,浮点外推法又做得更好(0.0034和0.0053),等等,没有很大的一致性。考虑到没有一种算法能够一致地产生比其他算法更好的均匀分布,这让我倾向于浮点外推,因为它的执行速度似乎比while-loop算法快。那么,选择浮点外推算法好吗?还是我的测试/结论不完全正确?

EN

回答 7

Stack Overflow用户

回答已采纳

发布于 2012-08-01 12:06:48

当随机数生成器(RAND_MAX+1)的输出数不能被期望的范围(max-min+1)均匀整除时,就会出现这个问题。由于将有一个从随机数到输出的一致映射,一些输出将被映射到更多的随机数。这是不管如何完成映射-你可以使用模块,除法,转换为浮点,无论你想出什么伏都教,基本的问题仍然存在。

问题的严重性很小,不需要严格要求的应用程序通常可以忽略它。范围越小,RAND_MAX越大,效果就越不明显。

我以你的例子程序为例,对它做了一些调整。首先,我创建了一个只有0-255范围的特殊版本的rand,以更好地演示效果。我对rangeRandomAlg2做了一些调整。最后,我将“球”的数量改为1000000,以提高一致性。您可以在这里看到结果:http://ideone.com/4P4HY

请注意,浮点版本产生两个紧密分组的概率,接近0.101或0.097,两者之间没有任何差别。这就是行动上的偏见。

我认为把这个叫做“Java的算法”有点误导--我相信它比Java要古老得多。

代码语言:javascript
运行
AI代码解释
复制
int rangeRandomAlg2 (int min, int max)
{
    int n = max - min + 1;
    int remainder = RAND_MAX % n;
    int x;
    do
    {
        x = rand();
    } while (x >= RAND_MAX - remainder);
    return min + x % n;
}
票数 12
EN

Stack Overflow用户

发布于 2012-08-01 04:08:52

问题是你在做模块操作。如果RAND_MAX可以被模整除,这是没有问题的,但通常不是这样的。作为一个非常精心设计的例子,假设RAND_MAX为11,模数为3。您将得到以下可能的随机数和下面的剩余数:

代码语言:javascript
运行
AI代码解释
复制
0 1 2 3 4 5 6 7 8 9 10
0 1 2 0 1 2 0 1 2 0 1

正如你所看到的,0和1的概率略高于2。

解决这一问题的一个选择是拒绝抽样:通过不允许上面的数字9和10,您可以使结果的分布再次均匀。最棘手的部分是弄清楚如何有效地做到这一点。在Java的java.util.Random.nextInt(int)方法中可以找到一个非常好的例子(一个花了我两天时间来理解它为什么工作的例子)。

Java的算法有点棘手的原因是它们避免了像乘法和除法这样的缓慢操作。如果你不在乎的话,你也可以用幼稚的方式去做:

代码语言:javascript
运行
AI代码解释
复制
int n = (int)(max - min + 1);
int remainder = RAND_MAX % n;
int x, output;
do {
  x = rand();
  output = x % n;
} while (x >= RAND_MAX - remainder);
return min + output;

编辑:在上面的代码中纠正了一个fencepost错误,现在它可以正常工作了。我还创建了一个小示例程序(C#;对0到15之间的数字采用统一的PRNG,并通过各种方式为0到6之间的数字构造PRNG ):

代码语言:javascript
运行
AI代码解释
复制
using System;

class Rand {
    static Random r = new Random();

    static int Rand16() {
        return r.Next(16);
    }

    static int Rand7Naive() {
        return Rand16() % 7;
    }

    static int Rand7Float() {
        return (int)(Rand16() / 16.0 * 7);
    }

    // corrected
    static int Rand7RejectionNaive() {
        int n = 7, remainder = 16 % n, x, output;
        do {
            x = Rand16();
            output = x % n;
        } while (x >= 16 - remainder);
        return output;
    }

    // adapted to fit the constraints of this example
    static int Rand7RejectionJava() {
        int n = 7, x, output;
        do {
            x = Rand16();
            output = x % n;
        } while (x - output + 6 > 15);
        return output;
    }

    static void Test(Func<int> rand, string name) {
        var buckets = new int[7];
        for (int i = 0; i < 10000000; i++) buckets[rand()]++;
        Console.WriteLine(name);
        for (int i = 0; i < 7; i++) Console.WriteLine("{0}\t{1}", i, buckets[i]);
    }

    static void Main() {
        Test(Rand7Naive, "Rand7Naive");
        Test(Rand7Float, "Rand7Float");
        Test(Rand7RejectionNaive, "Rand7RejectionNaive");
    }
}

结果如下(粘贴到Excel中并添加了单元格的条件着色,以使差异更加明显):

现在我修正了上述拒绝抽样中的错误,它的工作原理(在它偏置0之前)。正如您所看到的,浮点方法一点也不完美,它只是以不同的方式分配有偏数。

票数 14
EN

Stack Overflow用户

发布于 2012-08-01 04:12:37

很容易理解为什么这个算法会产生一个有偏差的样本。假设您的rand()函数从集合{0, 1, 2, 3, 4}返回一致整数。如果我想用它生成一个随机位01,我可以说是rand() % 2。set {0, 2, 4}给了我0,而set {1, 3}给了我1 --所以很明显,我用60%的可能性来采样0,用40%的可能性来采样1,一点也不一致!

要解决这个问题,您必须确保所需的范围除以随机数生成器的范围,或者在随机数生成器返回大于目标范围最大倍数的数字时丢弃结果。

在上面的例子中,目标范围为2,符合随机生成范围的最大倍数为4,因此我们丢弃任何不在集合{0, 1, 2, 3}中的样本并再次滚动。

票数 6
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/11758809

复制
相关文章
无偏估计
无偏估计:估计量的均值等于真实值,即具体每一次估计值可能大于真实值,也可能小于真实值,而不能总是大于或小于真实值(这就产生了系统误差)。
marsggbo
2018/08/10
1.4K0
无偏估计
生成无重复随机数
1 /** 2 * 无重复随机字符串 3 * num<62 num>=62或不传时位默认的62位 4 * @param {[int]} num [随机字符串长度] 5 * @return {[string]} [返回随机字符串] 6 */ 7 var ranNum = function(num) { 8 9 var str =
ProsperLee
2018/10/24
1.7K0
无偏估计
尽管在一次抽样中得到的估计值不一定恰好等于待估参数的真值,但在大量重复抽样时,所得到的估计值平均起来应与待估参数的真值相同。
小小杨
2021/10/13
1K0
Python生成随机整数数组的实用方法
在编程中,生成随机整数数组是一项非常常见的任务。本文将介绍如何使用Python语言来生成随机整数数组,帮助读者掌握这一有用的编程技巧。通过实际的代码示例,我们将逐步指导读者完成生成随机整数数组的过程,并提供一些实际应用的建议。
华科云商小彭
2023/10/09
6800
Python生成随机整数数组的实用方法
Java随机生成前N个不重复的整数
import java.io.BufferedOutputStream; import java.io.File; import java.io.FileNotFoundException; import java.io.FileOutputStream; import java.io.IOException; import java.io.OutputStream; import java.util.Random; /** 测试随机生成前N个不重复的整数 @author Administr
用户7999227
2021/09/23
1.5K0
JS生成随机数的算法
1>. Math.random() 表示生成 [0,1) 的数,所以 Math.random()*5 生成的都是 [0,4] 的随机整数。 2>Math.floor(num); 参数num为一个数值,函数结果为num的整数部分。 3>.Math.round(num); 参数num为一个数值,函数结果为num四舍五入后的整数。 4>.Math.ceil(n); 返回大于等于n的最小整数。 5>.random()%51+13我们可以看成两部分:rand()%51是产生 0~50 的随机数,后面+13保证 a 最小只能是 13,最大就是 50+13=63。
全栈程序员站长
2022/09/15
8.8K0
WWW2022 | 基于交叉成对排序的无偏推荐算法
现有大多数推荐系统都是对观测到的交互数据进行优化,而这些数据受到之前曝光机制的影响,会表现出许多偏差,比如流行偏差。经常使用的基于pointwise的二元交叉熵和pairwise的贝叶斯个性化排序损失函数,并不是专门设计来考虑观测数据的偏差的。因此,对损失进行优化的模型仍然会存在数据偏差,甚至会放大数据偏差。例如,少数受欢迎的商品占据了越来越多的曝光机会,严重损害了小众物品的推荐质量。
张小磊
2022/05/24
4680
WWW2022 | 基于交叉成对排序的无偏推荐算法
random生成随机整数 python_python中的random函数
在 Python 中用于生成随机数的模块是 random,在使用前需要 import.
全栈程序员站长
2022/11/09
1.1K0
random生成随机整数 python_python中的random函数
机器学习算法的随机数据生成
    在学习机器学习算法的过程中,我们经常需要数据来验证算法,调试参数。但是找到一组十分合适某种特定算法类型的数据样本却不那么容易。还好numpy, scikit-learn都提供了随机数据生成的功能,我们可以自己生成适合某一种模型的数据,用随机数据来做清洗,归一化,转换,然后选择模型与算法做拟合和预测。下面对scikit-learn和numpy生成数据样本的方法做一个总结。
刘建平Pinard
2018/08/14
1.1K0
机器学习算法的随机数据生成
生成不重复的随机数算法
本文转载http://blog.csdn.net/zhoufoxcn/article/details/5825093#comments
跟着阿笨一起玩NET
2018/09/18
1.6K0
随机数算法 java_最全的java随机数生成算法[通俗易懂]
大家好,又见面了,我是你们的朋友全栈君。 最全的java随机数生成算法 java随机数生成算法是怎么样的?下面yjbys小编为大家分享最新最全的java随机数生成算法,希望对大家学习有所帮助! 一个最
全栈程序员站长
2022/09/14
1K0
伪随机数生成算法
伪随机数生成算法在计算机科学领域应用广泛,比如枪击游戏里子弹命中扰动、数据科学里对样本进行随机采样、密码设计、仿真领域等等,背后都会用到伪随机数生成算法。
李拜六不开鑫
2018/08/22
1.8K0
伪随机数生成算法
伪随机数生成算法
伪随机数生成算法在计算机科学领域应用广泛,比如枪击游戏里子弹命中扰动、数据科学里对样本进行随机采样、密码设计、仿真领域等等,背后都会用到伪随机数生成算法。
李拜六不开鑫
2018/09/04
2.5K0
js随机生成一个[min,max]范围的整数,举一反三
如果是想带有小数的随机数,这里提供思路,产生两位数,然后将个位数转化为小数,十位数就是个位数,以此类推,这样就是有小数的啦。
啦啦啦啦
2023/02/27
1.4K0
无偏估计(Unbiased Estimator)「建议收藏」
一个简单的例子(https://www.zhihu.com/question/22983179/answer/23470969):
全栈程序员站长
2022/09/20
8250
无偏估计(Unbiased Estimator)「建议收藏」
PHP rand() 函数随机整数。
  如果没有提供可选参数 min 和 max,rand() 返回 0 到 RAND_MAX 之间的伪随机整数。例如,想要 5 到 15(包括 5 和 15)之间的随机数,用 rand(5, 15)。
睿儿网络郝刚
2020/09/16
2.6K0
杂谈:经典算法之随机数生成
tkinter库的那篇博客(python笔记:可视化界面写作尝试)真的是写的我心力憔悴啊,其实东西并不难,就是多,然后一开始又没有找到比较靠谱的官方文档,搞得我没写一个组件的应用就得去看源码,然后自己写代码尝试,搞得累的半死。
codename_cys
2021/03/25
6160
猜测1-100的随机整数
public static void main(String[] args) {
算法与编程之美
2023/01/03
9050
地统计基本概念:克里格插值、平稳假设、变异函数、基台、线性无偏最优等
  本文对插值、平稳假设、变异函数、克里格等常用的地学计算概念加以介绍,并对相关公式进行推导。
疯狂学习GIS
2023/09/23
1.3K0
地统计基本概念:克里格插值、平稳假设、变异函数、基台、线性无偏最优等
2018值得尝试的无参数全局优化新算法,所有测试取得最优结果
该文介绍了如何使用dlib库实现一个无参数、无梯度的黑盒优化算法,该算法可以用于机器学习和深度学习中的超参数优化,并且与现有的方法相比具有更好的性能。该算法可以用于解决机器学习中的特征选择问题,以及机器学习、深度学习中的超参数优化问题。
企鹅号小编
2018/01/05
1.3K0
2018值得尝试的无参数全局优化新算法,所有测试取得最优结果

相似问题

无偏随机整数生成器

50

无偏(随机?)选择算法

33

无偏随机列表生成

10

动态有偏随机选择算法

13

“随机卡片分配(扑克游戏)”的最优算法是什么?

18
添加站长 进交流群

领取专属 10元无门槛券

AI混元助手 在线答疑

扫码加入开发者社群
关注 腾讯云开发者公众号

洞察 腾讯核心技术

剖析业界实践案例

扫码关注腾讯云开发者公众号
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档