随机取样的实现

阅读《编程珠玑》取样问题，有感，遂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源码