1.1.39 关于随机数碰撞的警示

BinarySearchCase.java

package life.yanfeng.study.algorithm;

import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdOut;

import java.util.Arrays;
import java.util.Random;
import java.util.concurrent.ThreadLocalRandom;

// for 1.1.39
class BinarySearchCase {

    // 二分查找. 数据必须有序.
    static int binarySearch(int key, int[] a) {
        // 数据必须是有序的.
        int lo = 0;
        int hi = a.length -1;
        while (lo <= hi)
        {
            // 被查找的键, 要么不存在, 要么必须存在于 a[lo..hi] 之中.
            int mid = lo + (hi - lo) / 2;
            if (key < a[mid]) hi = mid -1;
            else if (key > a[mid]) lo = mid + 1;
            else return mid;
        }

        return -1;
    }

    static void findN(int T) {
        int[] items = {(int) Math.pow(10, 3), (int) Math.pow(10, 4), (int) Math.pow(10, 5), (int) Math.pow(10, 6)};
        for (int i = 0; i < items.length; i++) {
            int N = items[i];

            int sameTotal = 0;
            for (int j = 0; j < T; j++) {
                int [] a = new int[N];
                int [] b = new int[N];

                int min = 100000;
                int max = 1000000;
                for (int k = 0; k < N; k++) {
                    a[k] = ThreadLocalRandom.current().nextInt(min, max + 1);;
                    b[k] = ThreadLocalRandom.current().nextInt(min, max + 1);;
                }

                sameTotal += countSames(a, b);
            }

            double ava = (double) sameTotal / (double) T;

            StdOut.printf("N=%d\t\tT=%d\t\tava=%g\t\tava/N=%g\n", N, T, ava, ava/(double) N);
        }

        StdOut.println("-------");
    }

    static int countSames(int[] a, int[] b) {
        int count = 0;
        for (int i = 0; i < a.length; i++) {
            if (binarySearch(a[i], b) != -1) {
                count += 1;
            }
        }

        return count;
    }

    public static void main(String[] args) {
        int[] itemTs = {(int) Math.pow(10, 1), (int) Math.pow(10, 2), (int) Math.pow(10, 3)};

        for (int i = 0; i < itemTs.length; i++) {
            findN(itemTs[i]);
        }
    }
}

一些有趣的推论:

• 随机数 发生 碰撞, 并不 "罕见".
• 在核心业务, 可能重复触发的业务, 或者 数据数量级大于 10^4 的业务里, 不考虑和规避 "随机数" 碰撞, 将几乎必然引发灾难性问题.

N=1000		T=10		ava=0.00000		ava/N=0.00000
N=10000		T=10		ava=0.00000		ava/N=0.00000
N=100000		T=10		ava=2.10000		ava/N=2.10000e-05
N=1000000		T=10		ava=22.3000		ava/N=2.23000e-05
-------
N=1000		T=100		ava=0.0200000		ava/N=2.00000e-05
N=10000		T=100		ava=0.0700000		ava/N=7.00000e-06
N=100000		T=100		ava=1.92000		ava/N=1.92000e-05
N=1000000		T=100		ava=21.5600		ava/N=2.15600e-05
-------
N=1000		T=1000		ava=0.00700000		ava/N=7.00000e-06
N=10000		T=1000		ava=0.178000		ava/N=1.78000e-05
N=100000		T=1000		ava=1.80300		ava/N=1.80300e-05
N=1000000		T=1000		ava=21.8050		ava/N=2.18050e-05
-------