投递文章投递文章 投稿指南 RSS订阅RSS订阅

谈谈等概率不重复随机数生成算法中的大学问

来源:未知 IT堂 发布时间:2016-12-29 收藏 投稿 字体:【

 等概率不重复的生成随机数应该是在平时开发中常见的,也是面试中常问的基础之一。有多种实现方式,有人人都可以想到的,也有不容易想到的巧妙算法,那么当有人问你哪个实现方式更好的时候你该怎么回答呢?回答巧妙的算法比普通算法好?答案显而易见,首先要搞清楚应用场景和要解决的问题。这样才能判断一个算法或者方案的合适与否。

  接下来明确问题、提出多个解决方法,最后对比每个方法的优劣与使用场景。

  要求:

  可能有些具体的场景和问题需求都不一样,可以统一:在一定范围内等概率不重复的生成有限个随机数。具体的可以定义为,在[m,n]之间等概率的生成k个不相同的随机数。

   设计与实现:

  1.排重

  一个最简单的想法就是先生成再排重,直到生成k个随机数为止。把所有用到排重的算法都可以归为一类,包括利用Map、Set、BitMap、数组下标去重的都算。因为本质上是一样的,可能在排重的时候有些优化。

复制代码
public List<Integer> random1(int m, int n, int k) {

        if (k < 1 || k > n-m+1) {
            System.out.println("Params is illegal.");
        }
        
        Random random = new Random();

        List<Integer> ret = new ArrayList<Integer>();

        while (ret.size() < k) {
            Integer rand = random.nextInt(n-m+1)+m; //生成[m,n]之间的随机数
            if (!ret.contains(rand)) {
                ret.add(rand);
            }
        }

        return ret;
    }
复制代码

 

  排重的一种改进算法,数组下标去重:

复制代码
    //优化去重
    public List<Integer> random2(int m, int n, int k) {
        if (k < 1 || k > n-m+1) {
            System.out.println("Params is illegal.");
        }

        Random random = new Random();
        List<Integer> ret = new ArrayList<Integer>();
        int[] flag = new int[n-m+1];
        Arrays.fill(flag, 0);

        while (ret.size() < k) {
            Integer rand = random.nextInt(n-m+1)+m; //生成[m,n]之间的随机数
            if (flag[rand-m] == 0) {
                ret.add(rand);
                flag[rand-m] = 1;
            }
        }

        return ret;
    }
复制代码

  2.移动

  把[m,n]之间的数放到一个数组中,随机生成一个范围内的下标把选中的下标的值移动到最后一个,其余的向前移动。之后生成[m,n-1]范围内的下标,依次类推,直到生成了k个随机数。

 

复制代码
    //移动
    public List<Integer> random3(int m, int n, int k) {
        if (k < 1 || k > n-m+1) {
            System.out.println("Params is illegal.");
        }

        Random random = new Random();
        List<Integer> ret = new ArrayList<Integer>();
        int[] arr = new int[n-m+1];
        int j = m;
        for (int i=0; i<n-m+1; i++) {
            arr[i] = j++;
        }

        int cur = n-m+1;

        while (cur > 0 && n-m+1-cur < k) {
            int randIndex = random.nextInt(cur);
            int randValue = arr[randIndex];
            ret.add(randValue);
            for (int i=randIndex+1; i<cur; i++) {
                arr[i-1] = arr[i];
            }
            arr[cur-1] = randValue;
            cur --;
        }

        return ret;
    }
复制代码

 

  3.交换

 

  这种思路和上个移动的想法差不多,但不是再移动数组,而是交换。简单来说就是选择随机生成数组下标之后和下标为i-1的交换。直到每个元素都被交换过一遍。然后可以截取这个数组的k个元素。

    //交换
    public List<Integer> random4(int m, int n, int k) {
        if (k < 1 || k > n-m+1) {
            System.out.println("Params is illegal.");
        }

        Random random = new Random();
        List<Integer> ret = new ArrayList<Integer>();
        int[] arr = new int[n-m+1];
        int j = m;
        for (int i=0; i<n-m+1; i++) {
            arr[i] = j++;
        }

        for (int i=n-m; i>=0; i--) {
            int randIndex = random.nextInt(n-m+1);
            int t = arr[randIndex];
            arr[randIndex] = arr[i];
            arr[i] = t;
        }

        for (int i=0; i<k; i++) { //截取前k个
            ret.add(arr[i]);
        }

        return ret;
    }

 

  熟悉Java的同学都知道JDK中集合工具里有个shuffle洗牌方法,其核心思想就是随机交换。JDK-shuffle源码:

public static void shuffle(List<?> list, Random rnd) {
        int size = list.size();
        if (size < SHUFFLE_THRESHOLD || list instanceof RandomAccess) {
            for (int i=size; i>1; i--)
                swap(list, i-1, rnd.nextInt(i));
        } else {
            Object arr[] = list.toArray();

            // Shuffle array
            for (int i=size; i>1; i--)
                swap(arr, i-1, rnd.nextInt(i));

            // Dump array back into list
            // instead of using a raw type here, it's possible to capture
            // the wildcard but it will require a call to a supplementary
            // private method
            ListIterator it = list.listIterator();
            for (int i=0; i<arr.length; i++) {
                it.next();
                it.set(arr[i]);
            }
        }
    }

  比较:

  首先把问题分成几种情况,规定以下指标:数据范围大小amount=n-m+1,数据量大小k=[big, small],big代表接近amount,small代表更接近0。

  1.amount较小的情况下,其实差别不大,从时空复杂度上没有区分度。

  2.amount较大的情况下,k=small。排重要好于交换和移动。因为要选择出来的随机数数量要比范围小得多,这样一来如果要交换整个范围内的序列就会在效率上打折扣。因为在大范围选取个别随机数碰撞的概率较小所以排重工作就少了,这种情况下排重算法更好。

  3.amount较大的情况下,k=big。交换要好于移动和排重。因为在大范围内生成大量的随机数那么碰撞的几率就会变大,而且越往后越大,试想一下,如果要在100W个数中随机出99W个随机数,到生成第99W个随机数的时候碰撞率已经高达99%了。这是绝对忍受不了的。而反观交换算法,因为k比较接近amount所以交换整个序列不会浪费太多交换次数。遍历序列就能把整个序列等概率的shuffle一遍,然后截取k个即可。这种方法显然要高效许多。

顶一下
(0)
0%
踩一下
(0)
0%
  • 表情:
  •    
  • 评价:
用户名: 密码: 匿名 注册
最新评论 查看所有评论
About iTtang - 联系我们  - 专题列表 - 友情链接  -  高级搜索  -  帮助中心  -  您的意见