随机取样的实现
阅读《编程珠玑》取样问题，有感，遂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;
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018.10.05 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录