一道随机数题目的求解
有这样一道算法题:
给定一个能够生成均匀1~5随机枚举数的函数,请设计一个能够生成均匀1~7随机枚举数的函数。
就是说,有一个生成随机数的函数rand5,可能返回1、2、3、4、5这5个枚举值,其中每个值被返回的概率都是严格的1/5,现在需要设计一个类似的随机数函数rand7,可能返回1、2、3、4、5、6、7这几个枚举值,每个值被返回的概率都是严格的1/7。
先掩卷思考,脑海中浮现的思路包括:
调用rand5的结果除以5,再乘以7,这样的结果范围为7/5~7,并非所希望的结果;
反复调用rand5函数7次,结果再除以5,这样的结果范围为也为7/5 ~ 7,并非所希望的结果。
如果题目反过来呢,已知rand7,求rand5呢?
那我可以先调用rand7,看看结果,如果结果为1~5,直接返回;如果结果为6、7,继续重试不就得了?
那再回到现实,怎么根据rand5求rand7?
如果rand5 * 2的结果,范围是2~10,用上面类似的办法只能得到2~7的值,无法得到1,不合题意。
但是依然得到了一种启发,调用一次rand5,结果的各种可能性有5种,要映射到rand7的7种结果可能性,是不现实的。但是如果扔两次,在不考虑去重的情况下,结果有5*5=25种可能,用某种方式映射并保留那最终的7种可能性,却是一个值得去尝试的思路。
想到了5*5,于是尝试建立二维数组arr[5][5],那么数组的每一个元素都可以表示一种结果的可能性,在数组中取前7个元素,分别映射到1~7:
[1, 2, 3, 4, 5] [6, 7, 0, 0, 0] [0, 0, 0, 0, 0] [0, 0, 0, 0, 0] [0, 0, 0, 0, 0]
于是调用rand5两次,分别得到横坐标i和纵坐标j,如果arr[i][j]>0,则保留,否则重试。
这样的方法还不完美,因为25个数里面只有7个是有效的,大部分情况下都只能重试了,效率太低。
于是,在这个二维数组里面不止保留前7位,而是尽可能多地保留了所有7的完整倍数:
[1, 2, 3, 4, 5] [6, 7, 1, 2, 3] [4, 5, 6, 7, 1] [2, 3, 4, 5, 6] [7, 0, 0, 0, 0]
这样一来,大部分情况下,都会命中大于0的元素。
那就写出代码:
public class R { private static Random random = new Random(); private static int[][] arr = new int[][]{ {1,2,3,4,5}, {6,7,1,2,3}, {4,5,6,7,1}, {2,3,4,5,6}, {7,0,0,0,0} }; public static int rand5(){ random.setSeed(System.nanoTime()); return random.nextInt(5) + 1; } public static int rand7() { int i = rand5() - 1; int j = rand5() - 1; if (i == 4 && j >= 1) return rand7(); return arr[i][j]; } }
再写个main函数测试一下:
Map<Integer, Integer> counter = new HashMap<Integer, Integer>(); for (int i = 0; i < 10000000; i++) { int key = rand7(); Integer val = counter.get(key); if (null == val) val = 0; val++; counter.put(key, val); } for (Map.Entry<Integer, Integer> entry : counter.entrySet()) { System.out.println(entry.getKey() + ": " + entry.getValue()); }
重复测试一千万次,但是从结果看,分布却并不足够随机:
1: 1476605 2: 1764393 3: 1274549 4: 1219960 5: 1454842 6: 1425833 7: 1383818
重复测试了几次,都是输出2的情况居多。就这个数据量而言,我觉得这不是巧合。
为了让这个可能的差异更加明显,我把从rand5求rand7改成了从rand2求rand3:
public class R { private static Random random = new Random(); private static int[][] arr = new int[2][2]; static { arr[0][0] = 1; arr[0][1] = 2; arr[1][0] = 3; arr[1][1] = 0; } public static int rand2(){ random.setSeed(System.nanoTime()); return random.nextInt(2) + 1; } public static int rand3() { int i = rand2() - 1; int j = rand2() - 1; if (i == 1 && j == 1) return rand3(); return arr[i][j]; } }
再同样测试一千万次,结果却大跌眼镜:
One: 5043264 Two: 2472499 Three: 2484237
居然有一倍的差异。
怎么回事呢?我开始怀疑Java的这个伪随机函数得出的结果(在计算机的世界里要实现绝对随机是不可能的)不足够随机,于是写了个程序调用一千万次Java的伪随机函数来看结果:
Map<Integer, Integer> counter = new HashMap<Integer, Integer>(); for (int i = 0; i < 10000000; i++) { random.setSeed(System.nanoTime()); int key = random.nextInt(7) + 1; Integer val = counter.get(key); if (null == val) val = 0; val++; counter.put(key, val); } for (Map.Entry<Integer, Integer> entry : counter.entrySet()) { System.out.println(entry.getKey() + ": " + entry.getValue()); }
从结果来看分布非常均匀:
1: 1429576 2: 1425422 3: 1427902 4: 1427424 5: 1429457 6: 1430664 7: 1429555
一下子觉得百思不得其解。
于是我重新审视自己的思路,还是觉得没有什么问题。虽然总结果最初有25个,但是前21个的结果每个得到的可能性都是一致的,最后四个丢掉并重来,继续的测试依然是能保证结果概率均等的。本质上这种方式在统计学上面叫做“Reject Sampling”。
我请教了一下数学家@万精油墨绿,他说思路是没什么问题的,有问题的话,只能是代码的问题。
其实还有一种方法,本质上也是类似的,即根据:
5 * (rand5()-1) + rand5()
上面这个式子的结果可以得到从1到25所有的结果,并且显而易见这25个结果出现时,这两个rand5()都可以被唯一确定返回值,因此他们出现的概率都是彼此相等的。于是可以根据上面的公式,在结果大于3*7=21的时候重新计算,否则则返回除以7的余数即可:
public class R { private static Random random = new Random(); public static int rand5() { random.setSeed(System.nanoTime()); return random.nextInt(5) + 1; } public static int rand7() { int i = rand5(); int j = rand5(); int res = 5 * (i - 1) + j; if (res > 21) return rand7(); return res % 7 + 1; } }
同样跑了几次测试,每次测试一千万条数据,这次发现这个偏大的数跑到3上面去了:
1: 1383566 2: 1486463 3: 1748051 4: 1275854 5: 1219712 6: 1451438 7: 1434916
这么一来反而有点开窍的感觉了,我觉得是不是因为Java的伪随机数生成的方法,生成的数不足够随机呢?虽然看起来是随机的,但是那也只是看起来而已。当用“小随机”去生成“大随机”的时候,那些不随机的缺陷被放大了。而比较rand2生成rand3,和rand5生成rand7,明显是前者“放大”的倍数更大,因此最后得出的结果中,“随机性”显得差。
为了进一步检验这种猜想,我开始考虑能否让随机数的种子变化更大。因为目前使用的随机数种子是System.nanoTime(),这个方法看似纳秒,其实也只是:
Returns the current value of the most precise available system timer, in nanoseconds.
我想在我的实验中它远比毫秒精确,但是也只是保证了尽可能精确而已。
那好,要验证或者说部分验证这样的猜想,现在假设这样的猜想是正确的,那么可以得出这样的推论:
如果随机数种子换成System.currentTimeMillis(),也就是说,换成毫秒,那么最后的结果应该是更不随机;
如果我在每次取随机数之前休息几毫秒,使得每两次之间的时间种子差异增大,应该能够看到最终的结果随机性增加。
(注,我测试的版本下JDK对于设置的种子的处理方式是:seed = (seed ^ 0x5DEECE66DL) & ((1L << 48) -1)。)
好吧,现在来验证第一条,为了尽可能使得结果明显,使用rand2生成rand3的那个方案。把使用纳秒作为随机数种子改成使用毫秒作为随机数种子,结果居然是:
One: 10000000 Two: 0 Three: 0
换言之,二维数组中横坐标和纵坐标居然在一千万次测试当中,得到的都是一样的结果,即绝大多数情况下求i和j的操作都在同一个毫秒量级内完成。
现在来验证第二条,在每次取随机数前,休眠3毫秒,当然,这个3毫秒肯定也是不精确的3毫秒。为了在增加休眠时间的情况下,能够在我的耐心时间范围内得到最终结果,我没法测试一千万次了,我的测试用例改成了测试一万次,结果为:
One: 3691 Two: 3103 Three: 3206
果然,分布的均匀性要好了很多。
还蛮好玩的。
建议继续学习:
- Mysql的随机读取 (阅读:6890)
- HBase随机写以及随机读性能测试 (阅读:6503)
- PHP概率算法(适用于抽奖、随机广告) (阅读:3258)
- 几个随机算法 (阅读:2617)
- PHP伪随机发生器 (阅读:2333)
- 趣题:随机折断的木棒 (阅读:2275)
扫一扫订阅我的微信号:IT技术博客大学习
- 作者:四火 来源: 四火的唠叨
- 标签: 随机
- 发布时间:2016-03-09 23:24:02
- [69] Twitter/微博客的学习摘要
- [65] 如何拿下简短的域名
- [64] IOS安全–浅谈关于IOS加固的几种方法
- [63] android 开发入门
- [62] Go Reflect 性能
- [62] find命令的一点注意事项
- [60] 流程管理与用户研究
- [58] 图书馆的世界纪录
- [58] 读书笔记-壹百度:百度十年千倍的29条法则
- [58] Oracle MTS模式下 进程地址与会话信