随机取样的实现

阅读《编程珠玑》取样问题，有感，遂Java实现。

需求

程序的输入包含两个整数m和n，其中 m <n 。输出是 0~n-1 范围内 m 个随机整数的有序列表，不允许重复。从概率的角度说，我们希望得到没有重复的有序选择，其中每个选择出现的概率相等。

简单来说，就是从n个样本中随机抽取m个。

思路

随机取样，大致有两种思路。伪代码如下：

// 思路一
while(已抽取样本数 < 需要抽取的样本数){
      随机抽取样本a
      if(a不在已抽取样本中){
            将a加入已抽取样本
            已抽取样本数++
      }
}
 
// 思路二
将所有样本顺序打乱
按顺序取走需要的样本数

思路一通过循环随机直至样本数满足条件，思路二通过打乱样本顺序的方式取样。

源码

用Java代码实现后，自测在各种情况下，思路一性能都好于思路二。下面是源码。

经优化后的思路一（性能非常好，所以分享，哈哈～）。
主要优化点：

• 利用数组的快速定位来校验某个样本是否已被抽取；
• 如果取样数大于总样本数的一半，那就随机抽取其补集（另一小半）。

    /**
     * 随机取样
     *
     * @param bound 样本总数
     * @param count 需要抽取的样本数
     * @return 返回一个有序数组
     */
    private static int[] getRandomSamples(int bound, int count) {
        if (bound < 1 || count < 1 || bound <= count)
            return null;

        boolean[] fillArray = new boolean[bound];
        for (int i = 0; i < bound; i++) {
            fillArray[i] = false; //用false标示未填充,true表示已填充。
        }

        Random random = new Random();
        int fillCount = 0;
        final int randomNumCount = Math.min(count, bound - count); //随机填充的数目不超过一半
        while (fillCount < randomNumCount) {
            int num = random.nextInt(bound);
            if (!fillArray[num]) {
                fillArray[num] = true;
                fillCount++;
            }
        }

        int[] samples = new int[count];
        //如果随机抽取的数量与所需相等，则取该集合；否则取补集。
        if (randomNumCount == count) {
            int index = 0;
            for (int i = 0; i < bound; i++) {
                if (fillArray[i])
                    samples[index++] = i;
            }
        } else {
            //取补集
            int index = 0;
            for (int i = 0; i < bound; i++) {
                if (!fillArray[i])
                    samples[index++] = i;
            }
        }
        return samples;
    }

思路二，调用java默认的洗牌方法来实现，性能不如思路一的实现（常见数据量下耗时大概是上面代码的2～10倍；对于极大范围取样，比如1亿样本里随机抽取500万，耗时是上面代码的100倍）。

    /**
     * 通过洗牌的方式随机取样
     */
    private static int[] getRandomSamples2(int bound, int count) {
        if (bound < 1 || count < 1 || bound <= count)
            return null;
        List<Integer> list = new ArrayList<>(bound);
        for (int i = 0; i < bound; i++) {
            list.add(i);
        }
        Collections.shuffle(list);
        int[] samples = new int[count];
        for (int i = 0; i < count; i++) {
            samples[i] = list.get(i);
        }
        return samples;
    }

Gist 随机取样Java源码