专栏首页lhyt前端之路js随机数生成器的扩展0.前言1.扩展+分区2.二进制法3. 总结

js随机数生成器的扩展0.前言1.扩展+分区2.二进制法3. 总结

0.前言

给你一个能生成随机整数1-7的函数,就叫他生成器get7吧,用它来生成一个1-11的随机整数,不能使用random,而且要等概率。

getx就是指一个能生成1到x的随机数的函数

主角:get7(你们所有人都没有random这个技能,全都disable了)

function  get7() {
	return ~~(Math.random()*7)+1 //规则:整篇文章,唯一能用random的地方
}
复制代码

1.扩展+分区

既然是扩展,那么我给小范围随机数生成器扩展个几倍,再截取目标随机数范围不就得了。 先问一下,怎么用get7能实现一个合格的get14?这样子?

function get14(){
	return get7() +get7() 
}
复制代码

我们来测试一下:

    	var obj = Object.create(null)
    	for(var i = 0;i<1000000;i++){
    		var n = get14();
    		if(!obj[n]){
    			obj[n] = 1
    		}else{
    			obj[n] ++
    		}
    	}
    	console.log(obj)
复制代码

先不说最小值的问题,首先,他不是等概率的序列 那么我们探讨另一个问题,究竟get14能不能直接用get7加减乘除就表示出来?

喂,说get7() 乘以11/7的那个,你确定没问题?

1.1 扩展

既然是小范围随机扩展到大范围,那么肯定离不开小范围随机数生成器get7的多次调用。当然我们最终目标很明确,目标随机数生成器get11,它的每一个随机数都会等概率映射到get7的扩展序列里面:

然后我们很快就可以想到一个公式:

a*(getx - 1) + getx
复制代码

a是个整数,整个公式含义是,把getx扩展为a倍,并且实现等概率分布。比如x是3,我们想扩展成2倍,a=2,就是2*(get3 - 1) + get3,范围是1-7,但是,我们看看概率:

 x\y   1  2  3
  0    1  2  3 
  2    3  4  5
  4    5  6  7   =》1-7的概率是1:1:2:1:2:1:1
复制代码

明显这个公式还有前提

1.2 a取值范围

我们再看a = 1:

x\y 1  2  3
 0  1  2  3 
 1  2  3  4
 2  3  4  5   =》1-5的概率是1:2:3:2:1
复制代码

好像矩阵每一行都是有交集

//如果a是3,ran3 - 1生成0-6 ,ran3 生成 1-3
x\y  1  2  3
0  1  2  3 
3  4  5  6
6  7  8  9   =》1-9等概率

//如果a是4,ran3 - 1生成0-8 ,ran3 生成 1-3
x\y 1  2  3
0  1  2  3 
4  5  6  7
8  9  10 11   =》数字都是等概率出现的,只是中间缺失了一些数,但不影响大局
复制代码

所以,只要保证所有的数等概率出现,先满足映射表最大值大于等于自身的平方(3*3 = 9,即a至少要是3) 为什么呢?因为不足本身,必然有交集,就像上面1和2两个矩阵每一行都有交集,只要大于本身的大小,矩阵每一行就不会有交集,没有交集,那它们就可以等概率 所以,对于7想扩展一个等概率序列,get14(get小于49都是没用,不是等概率)显然是没用的,起码要get49,此后所有的序列长度都是49。所以一个get14得通过get49得到,我们也可以从get49到get11了

1.3 从get49到get11

function get49(){
    var n = 7*(get7()-1) + get7() //a*(getx - 1) + getx,a取7,不信自己打印看一下
    return  n
}
var obj = Object.create(null)
for(var i = 0;i<1000000;i++){
	var n = get49();
	if(!obj[n]){
		obj[n] = 1
	}else{
		obj[n] ++
	}
}
console.log(obj)
复制代码

既然我们看见全部元素等概率出现了,那我们只要把多余的排除掉就行,即是遇到不是我们想要的范围那些,重新生成一次。

function get11(){
    var n = 7*(get7()-1) + get7() //a*(getx - 1) + getx,a取7,不信自己打印看一下
    return  n > 11?get11():n
}
复制代码

改改get49就行,对了,好像扩展数组太多没用的了,我们应该提高扩展数组的利用率,并且减小递归次数

function get11(){
	var n = 7*(get7()-1) + get7() 
	return  n>44?get11():~~((n-1) / 4)+1
}
复制代码

2.二进制法

对小随机数函数进行二进制划分,一半表示1一半表示0,然后用二进制表示大随机数,再去除多余的 get7到get11,8<11<16,我们取4位二进制,也就是取4次get7 因为7是奇数,我们就去掉一个吧,那我们去掉1,当遇到1重新生成一次,剩下的划分二等分

//获取二进制序列
function getBinary(){
	var n = get7()
	if(n>4){
		return 1
	}else if(n>1){
		return 0
	}else{
		return getBinary()
	}
}
//二进制序列转化回去
function get11_by_binary(){
	var res = ''
	for(var i = 0;i<4;i++){
		res += getBinary()
	}
	res = parseInt(res,2)
	return res>11?get11_by_binary():res
}
复制代码

当然,性能会差很多,因为太多遍历了。通用版本也不难,可以自己封装一个。

3. 总结

其实第一种方法叫做拒绝采样。我们知道等概率生成某个范围的随机数,想通过这个函数生成一个更小范围的随机数,就应该这样子:超过预期范围,重新抽取,所以叫做拒绝采样。 基本的操作:

//我们还是用get7获取1到小于7的随机数
function getn(n){//n是小于7的正整数
    var num = get7()
    return num > n?getn(n):num
}

//while形式
function getn(n){
	var t
	do{
		t = get7()
	}while(t>n)
	return t
}
复制代码

那我们get14就可以很灵活获得了,7*2得到14是吧,那就来:

function get14(){
	var t
	do{
		t = get7()
	}while(t>2)//我们就叫他get2吧
	return get7() + 7 * (t -1) //上面的a*(getx - 1) + getx公式的变种,这个a等于7
}
复制代码

都get14了,那get11还会远吗,大于11就拒绝采样咯。前面说先要get49?这只是一个循序渐进的过程,这样子你可以深刻理解到这个过程要怎么来,是不是感觉拒绝采样很灵活?

公式推广: 已知生成器getn能生成1-n的随机数,那么由getn拒绝采样得到的新生成器geta和getb(a,b都不大于n),可以生成get(a*b):

get(a*b) = geta + a*(getb-1)//公式是对称的,可以交换a和b


//上面的例子用公式解释
get14() = get7() + 7 * (get2() -1) = get2() + 2*(get7() -1)
//其实get10也可以
get10() = get5() + 5 * (get2() -1) = get2() + 2*(get5() -1)
复制代码

get7能获得get2,那get14就可以得到了还可以获得get5,那get10也是可以做到。刚刚好就是最完美的,如果目标生成器是质数,就让拒绝采样次数尽量少,也就是尽量靠近目标。这种随机数扩展, 套路就是超过的拒绝采样,不足的利用加法和乘法使得刚刚好到目标范围或者超过目标

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 记一次preact迁移到react16.6.7的经历

    preact作为备胎,但是具有体积小,diff算法优化过的特点,简单活动页用上它是不错的选择。但是考虑到react令人兴奋的新特性,preact并没有按时更新去...

    lhyt
  • 内功修炼之lodash——function系列(面试高频考点)

    本文实现方法都是看效果倒推实现方法,并进行一些拓展和思考,和源码无关。lodash这个库在这里更像一个题库,给我们刷题的

    lhyt
  • 一点点css的基础原理总结0.前言1.包含块(CB)2.宽和高3.BFC4.行内元素5. 垂直方向的margin6.盒子模型

    CSS属性非常多,如果说死记的话,是不容易的,我们了解他的原理,其他不常见的属性都是手到擒来

    lhyt
  • 数据工厂里的年轻人

    量子位
  • 目标检测竞赛利器:中星微一步法模型获国际算法竞赛第一名!

    【新智元导读】近日,在国际计算机视觉竞赛PASCAL VOC,中星微以89.0分的总成绩位列第一,获得目标检测单模型第一名。获胜的模型是一步法的目标检测模型,本...

    新智元
  • 阶段01Java基础day04JAVA循环语句

    声明:本文为原创,作者为 对弈,转载时请保留本声明及附带文章链接:http://www.duiyi.xyz/c%e5%ae%9e%e7%8e%b0%e9%9b%...

    对弈
  • Java基础笔记04

    dreamkong
  • 工作中,你真的会表达数据吗?

    来源 | 《用数据讲故事》 我们要的不是数据,而是数据告诉我们的事实 在幻灯片中,数据的作用一直很受重视。在工作场合,饼图、柱形图、条形图、折线图、散点图充斥在...

    CSDN技术头条
  • 深入理解JVM:元空间大小详细解析

    JVM加载类的时候,需要记录类的元数据,这些数据会保存在一个单独的内存区域内,在Java 7里,这个空间被称为永久代(Permgen),在Java 8里,使用元...

    程序员追风
  • 从小作坊到大生产,AI数据标注转捩点

    2018年初,「甲子光年」曾发布《“数据折叠”:今天,那些人工智能背后“标数据的人”正在回家》。劳动密集型是人们对数据标注行业的固有印象,基层数据标注员被视为数...

    用户2908108

扫码关注云+社区

领取腾讯云代金券