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

复制
相关文章
Swift基础 继承
翻译自:https://docs.swift.org/swift-book/LanguageGuide/Inheritance.html
郭顺发
2023/07/17
1180
Swift2.1-继承继承
一个类可以从另一个类继承方法,属性和其他的特性。当一个类从另一个类继承的时候,继承类被称为子类,这个类继承的类被称为父类。在Swift中,继承是基本的,从Swift中的其他类型来区分类的一种行为。
hrscy
2018/08/30
4620
Swift专题讲解十四——继承 原
        Swift中,一个类可以从另一个类继承方法、属性、下标及其他特性。当一个类继承于另一个类时,这个类被称为子类,所继承的类被称为父类。在Swift中,继承是类区别于其他类型的主要特征。子类除了可以调用父类的属性,下标,方法外,其也可以对父类的属性,下标,方法进行覆写。
珲少
2018/08/15
2870
Jekyll-Admin-Mac 开发纪要-左侧菜单栏
本文章文字大约 4500字,大概花费 10分钟阅读。本文章设计的图片比较多,流量党慎入!。
君赏
2018/08/31
2.1K2
Jekyll-Admin-Mac 开发纪要-左侧菜单栏
泛型的继承和通配符,同时归纳集合部分的面试点
    在定义泛型时,我们可以通过extends来限定泛型类型的上限,也可以通过super来限定下限,这两个限定字一般会和?等关键字搭配使用。     比如有这样的代码List<? super Fat
用户1153489
2018/01/12
8810
怎么让继承的类直接使用XIB的布局试图
最近做的一个小工具,一键替换key,就是为了解放双手,不然每次运行测试和正式的版本都要手动的替换key。
君赏
2018/08/31
1.1K0
怎么让继承的类直接使用XIB的布局试图
Swift的属性,方法,下标脚本以及继承
从这篇章节起,Swift编程语言指南大部分的重要内容在于概念,代码并非太多。理解Swift的面向对象理念,语法以及类结构,构造析构过程对于非常好的应用Swift语言将会有比較大的帮助。
全栈程序员站长
2022/07/14
8880
Swift的属性,方法,下标脚本以及继承
Mac开发跬步积累(二):NSViewController 转场动画精耕细作
在macOS 10.10之后,关于NSViewController,苹果公司专门在一个extension中提供了四个方法用来处理控制器之间的关系以及切换转场处理.
代码行者
2018/08/23
2.8K0
Mac开发跬步积累(二):NSViewController 转场动画精耕细作
Mac OS开发系列之NSImageView
最近研究下Mac开发的一些技巧,有兴趣的朋友关注我就对了! 争取在工作之余把Mac开发给拿下! //初始化NSImageView并设置它的大小 NSImageView *imgView = [[NSImageView alloc]initWithFrame:CGRectMake(self.view.frame.size.width/2-35, 100, 70, 70)]; //给图片赋值和iOS开发是一样的 imgView.image = [NSImage imageNamed:@"1"]; [self
Bison
2018/06/28
9290
Swift vs. Kotlin 漫谈系列之类与继承
Kotlin 君和 Swift 君在一个团队一起开发已经很久了,由于平台的差异性,他们经常会进行一些技术上的交流(PK),《Kotlin vs. Swift漫谈》系列就是他们在互相切磋是的语录。内容会
用户1907613
2018/07/20
3.7K0
窥探Swift之类的继承与类的访问权限
  上一篇博客《窥探Swift之别具一格的Struct和Class》的博客可谓是给Swift中的类开了个头。关于类的内容还有很多,今天就来搞一下类中的继承以及类的访问权限。说到类的继承,接触过面向对象编程(OOP)的小伙伴并不陌生,继承就是OOP编程中几大特征之一,所以还是有必要把类的继承拎出来聊聊的。说到访问权限,这个在OOP编程中也是不可或缺的。如果你接触过其他OOP的语言,你应该对private, public, protected并不陌生。在Swift这么面向对象的编程语言中,也有类似的概念,不过其
lizelu
2018/01/11
1.5K0
窥探Swift之类的继承与类的访问权限
继承和多态
刚才我们提到了,可以在已有类的基础上创建新类,这其中的一种做法就是让一个类从另一个类那里将属性和方法直接继承下来,从而减少重复代码的编写。提供继承信息的我们称之为父类,也叫超类或基类;得到继承信息的我们称之为子类,也叫派生类或衍生类。子类除了继承父类提供的属性和方法,还可以定义自己特有的属性和方法,所以子类比父类拥有的更多的能力,在实际开发中,我们经常会用子类对象去替换掉一个父类对象,这是面向对象编程中一个常见的行为,对应的原则称之为里氏替换原则。下面我们先看一个继承的例子。
用户8442333
2021/05/19
4280
[Maven进阶]聚合和继承
我们的项目已经从以前的单模块,变成了现在的多模块开发。项目一旦变成了多模块开发以后,就会引发一些问题,在这一节中我们会介绍两个内容聚合和继承,用这两个知识来解决下分模块后的一些问题。
十八岁讨厌编程
2022/12/10
7870
Swift和OC互调(一)Swift调用OCOC调用Swift
整理之前学习swift的笔记,虽然现在看起来很简单,但还是想分享出来。 (一)Swift调用OC 假设:我们的项目是Swift的。项目中用到了OC写的一些类。那么怎么让Swift调用OC类呢?如下图:
VV木公子
2018/06/05
13.6K0
JS原型继承和类式继承
类式继承(构造函数) JS中其实是没有类的概念的,所谓的类也是模拟出来的。特别是当我们是用new 关键字的时候,就使得“类”的概念就越像其他语言中的类了。类式继承是在函数对象内调用父类的构造函数,使得自身获得父类的方法和属性。call和apply方法为类式继承提供了支持。通过改变this的作用环境,使得子类本身具有父类的各种属性。 var father = function() { this.age = 52; this.say = function() { alert('hello
庞小明
2018/03/07
3.5K0
JS原型继承和类式继承
继承和多态
这里继承和多态的概念与java的概念差不多。概念还是需要多次理解才能透彻。感觉类和实例的概念还是不能深刻理解。再次复习下吧。
一点儿也不潇洒
2018/08/02
3690
Swift之 ? 和 !
Swift语言使用var定义变量,但和别的语言不同,Swift里不会自动给变量赋初始值,也就是说变量不会有默认值,所以要求使用变量之前必须要对其初始化。如果在使用变量之前不进行初始化就会报错:
JoeyBlue
2021/09/07
5120
Swift中? 、! 和 ??
Swift中是可以声明一个没有初始值的属性, Swift中引入了可选类型(Optional)来解决这一问题。它的定义是通过在类型声明后加一个 ? 操作符完成的。 例如: var name: Stri
赵哥窟
2020/08/17
1.6K0
继承和多态
在OOP程序设计中,当定义一个class的时候,可从某个现有的class继承 新的class称为子类(Subclass),而被继承的class称为基类、父类或超类(Base class、Super class) 格式:
py3study
2020/01/15
3960
原型式继承和类式继承
Java和JavaScript都是面向对象的语言,但二者的继承方式截然不同。前者采用类式继承(classical inheritence),也是大多数面向对象语言的继承方式。而后者采用原型式继承(prototype ineritence),因此称JavaScript为基于对象更加合适。
Chor
2019/11/07
1.5K0

相似问题

Swift NSViewController

23

使用错误Swift创建NSViewController

10

Swift和继承

20

NSImageView和NSUndoManager

10

NSViewController和绑定

10
添加站长 进交流群

领取专属 10元无门槛券

AI混元助手 在线答疑

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

洞察 腾讯核心技术

剖析业界实践案例

扫码关注腾讯云开发者公众号
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档
查看详情【社区公告】 技术创作特训营有奖征文