一道随机数题目的求解

random 有这样一道算法题:

给定一个能够生成均匀 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.

我想在我的实验中它远比毫秒精确,但是也只是保证了尽可能精确而已。

那好,要验证或者说部分验证这样的猜想,现在假设这样的猜想是正确的,那么可以得出这样的推论:

  1. 如果随机数种子换成 System.currentTimeMillis(),也就是说,换成毫秒,那么最后的结果应该是更不随机;
  2. 如果我在每次取随机数之前休息几毫秒,使得每两次之间的时间种子差异增大,应该能够看到最终的结果随机性增加。

(注,我测试的版本下 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

果然,分布的均匀性要好了很多。

问题还没完,为了尽可能消除这种种子相似所带来的伪随机性,其实可以只初始化一遍种子,然后在迭代方法内部不断调用 Random 的 nextInt 方法就好了,这也是在这种情形下更加合理的使用随机数生成器的方式:

public class R {
	private static Random random = new Random(System.nanoTime());
	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(){
		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];
	}

	public static void main(String[] args) {
		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: 1428864
2: 1429574
3: 1427055
4: 1429929
5: 1429162
6: 1426933
7: 1428483

还蛮好玩的。

文章未经特殊标明皆为本人原创,未经许可不得用于任何商业用途,转载请保持完整性并注明来源链接 《四火的唠叨》

22,693 次阅读

12 thoughts on “一道随机数题目的求解

  1. 其实你可以视无限多次 rand5() 得到的结果构造一个 5 进制数,把这个 5 进制数转换为 7 进制数,即得到连续的 rand7() 的结果了。

    所以不需要 reject sampling。把除法得到余数留着下次继续算就可以了。

    随手写了个 js 的实现:

    let x = 1, v = 0
    function rand7() {
    while (x < 7) {
    x *= 5
    v *= 5
    v += rand5() - 1
    }
    const result = v % 7
    v -= result
    v /= 7
    x /= 7
    return result + 1
    }

  2. 结论虽对,过程错误太多
    比如
    如果 rand5 * 2 的,范围是 2~10,只能得到 2~7 的值。
    如果能得到 2~10,减一不就是 1~9,然后不就可以 2~7,可惜的是得到的不是 2~10 而是 {2,4,6,8,10}
    再比如/5×7,1-5 虽然是 7/5~7,但是减 1 之后/4×6 再+1,不就是 1~7 了,不行的根本原因是因为计算机做除法不靠谱
    楼主根本没明白这题

    1. “ 减一不就是 1~9,然后不就可以 2~7” — 这个逻辑怎么得来的?
      “可惜的是得到的不是 2~10 而是 {2,4,6,8,10}” — 这是什么意思?
      “再比如/5×7,1-5 虽然是 7/5~7,但是减 1 之后/4×6 再+1,不就是 1~7 了” — 我不明白你说的意思

      1. 我是按照你的意思写的
        你说“如果 rand5 * 2 的,范围是 2~10,只能得到 2~7 的值”
        按照这个逻辑,rand5*2 – 1,范围不就是 1~9,能得到 1~7 的值
        问题是原题给的 rand5 函数,输出结果是离散的,结果是 {1,2,3,4,5}, 所以 rand5 * 2 结果是 {2,4,6,8,10}
        同样/5×7 的结果是 {7/5,14/5,21/5,28/5,7}
        算了,您当我胡说吧

        1. “按照这个逻辑,rand5*2 – 1,范围不就是 1~9,能得到 1~7 的值”,是的,我明白你的意思了,你这话是对的。这个乘以 2 的办法是不对的,因为结果是离散的。
          所以这里的问题在于离散值如果等比例放到或者缩小,所得到的离散值的个数,和原来是相同的,换言之,rand5 只能得到 5 个离散值,如果只是乘以或者除以某个数,也只能得到 5 个离散值。

          不过我还是不明白你说的“计算机做除法不靠谱”。

    1. 没错,有这种可能,因为 Sampling reject 的关系,但是我还可以在这种情况出现时,选择上一次的执行结果,这样就不会出现这种可能在有限步中完不成的情况了。这也是不影响概率分配的。

  3. 渐进的思路比较有意思,所以问题确实 shi 由于 java 的伪随机引起,通过 sleep 修改 seed,可以消除这种伪随机被放大的因素?

  4. random 不應每次調用時 setSeed,而應只在構造函數裡初始化一下,不然如果時間精度不足,連續調用時就會一直使用同一個種子,導致結果不夠隨機。
    至於那個跑 10000000 次的程序,我用 Ideone 跑了一下,結果還是很不均勻:
    https://ideone.com/ckd6BN
    1: 1427164
    2: 1435913
    3: 1395810
    4: 1447688
    5: 1415879
    6: 1472439
    7: 1405107
    而把 random.setSeed(System.nanoTime()); 放在 for 外面則沒問題(而且還快很多):
    https://ideone.com/luYWz4
    1: 1429394
    2: 1429356
    3: 1429751
    4: 1429016
    5: 1426168
    6: 1427692
    7: 1428623
    至於為甚麼你會得到均勻的結果,我猜是因為 Map 太慢,讓 setSeed 的間隔足夠長。
    你可以改用 int[] 試試:
    https://ideone.com/fZXxnx

            int[] map = new int[7];
            for (int i = 0; i < 7; i++) {
            map[i] = 0;
            }
            for (int i = 0; i < 10000000; i++) {
        random.setSeed(System.nanoTime());
                map[random.nextInt(7)]++;
            }
            for (int i = 0; i < 7; i++) {
                System.out.println(i + ": " + map[i]);
            }

     

    1. 首先,感谢有价值的回复。

      其次,

      1. “不應每次調用時 setSeed,而應只在構造函數裡初始化一下”,这个确实如此,而且这确实也是更加合理的方法,我把这个办法更新到我的文中去。

      2. “我猜是因為 Map 太慢,讓 setSeed 的間隔足夠長”,那好,我把根据 rand2 求 rand3 的那个程序也使用 Map 的机制来实现一遍:


      public class R {
      private static Random random = new Random();
      private static int[][] arr = new int[][]{
      {1,2},
      {3,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];
      }

      public static void main(String[] args) {
      Map counter = new HashMap();

      for (int i = 0; i < 10000000; i++) { int key = rand3(); Integer val = counter.get(key); if (null == val) val = 0; val++; counter.put(key, val); } for (Map.Entry entry : counter.entrySet()) {
      System.out.println(entry.getKey() + ": " + entry.getValue());
      }
      }
      }

      结果:

      1: 4741216
      2: 2602806
      3: 2655978
      因此,可见和是否使用 Map 无关。

发表评论

电子邮件地址不会被公开。

back to top