閱讀《編程珠璣》取樣問題辨嗽，有感赌渣，遂Java實現(xiàn)魏铅。
需求
程序的輸入包含兩個整數(shù)m和n，其中 m <n 坚芜。輸出是 0~n-1 范圍內(nèi) m 個隨機整數(shù)的有序列表览芳，不允許重復(fù)。從概率的角度說鸿竖，我們希望得到?jīng)]有重復(fù)的有序選擇沧竟，其中每個選擇出現(xiàn)的概率相等铸敏。
簡單來說，就是從n個樣本中隨機抽取m個悟泵。
思路
隨機取樣杈笔，大致有兩種思路。偽代碼如下：
// 思路一
while(已抽取樣本數(shù) < 需要抽取的樣本數(shù)){
隨機抽取樣本a
if(a不在已抽取樣本中){
將a加入已抽取樣本
已抽取樣本數(shù)++
}
}
// 思路二
將所有樣本順序打亂
按順序取走需要的樣本數(shù)
思路一通過循環(huán)隨機直至樣本數(shù)滿足條件糕非，思路二通過打亂樣本順序的方式取樣蒙具。
源碼
用Java代碼實現(xiàn)后，自測在各種情況下朽肥，思路一性能都好于思路二禁筏。下面是源碼。
經(jīng)優(yōu)化后的思路一（性能非常好鞠呈，所以分享融师，哈哈～）。
主要優(yōu)化點：
- 利用數(shù)組的快速定位來校驗?zāi)硞€樣本是否已被抽纫狭摺；
- 如果取樣數(shù)大于總樣本數(shù)的一半舀射，那就隨機抽取其補集（另一小半）窘茁。
/**
* 隨機取樣
*
* @param bound 樣本總數(shù)
* @param count 需要抽取的樣本數(shù)
* @return 返回一個有序數(shù)組
*/
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標(biāo)示未填充,true表示已填充。
}
Random random = new Random();
int fillCount = 0;
final int randomNumCount = Math.min(count, bound - count); //隨機填充的數(shù)目不超過一半
while (fillCount < randomNumCount) {
int num = random.nextInt(bound);
if (!fillArray[num]) {
fillArray[num] = true;
fillCount++;
}
}
int[] samples = new int[count];
//如果隨機抽取的數(shù)量與所需相等脆烟，則取該集合山林；否則取補集。
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;
}
思路二邢羔，調(diào)用java默認的洗牌方法來實現(xiàn)驼抹，性能不如思路一的實現(xiàn)（常見數(shù)據(jù)量下耗時大概是上面代碼的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;
}
