import java.util.ArrayList;
import java.util.List;
import java.util.Random;
/*
* 思路：蓄水池抽样算法
1.如果接收的数据量小于m，则依次放入蓄水池。
2.当接收到第i个数据时，i >= m，在[0, i]范围内取以随机数d，若d的落在[0, m-1]范围内，则用接收到的第i个数据去替换蓄水池中的第d个数据。
重复步骤2。
3.算法的精妙之处在于：当处理完所有的数据时，蓄水池中的每个数据都是以m/N的概率获得的。
* */
public class Pool<T> {
private final static Random random = new Random();
private List<T> list;// 中奖的人
private int num;// 池子大小
private int count;// 记录奖池处理了多少人
public List<T> getList() {
return list;
}
public void setList(List<T> list) {
this.list = list;
}
public int getNum() {
return num;
}
public void setNum(int num) {
this.num = num;
}
public int getCount() {
return count;
}
public void setCount(int count) {
this.count = count;
}
public static Random getRandom() {
return random;
}
public Pool(int n) {
this.num = n;
list = new ArrayList<T>(n);
}
private void add(T t) {
if (count < num) {
list.add(t);
count++;
} else {
final int rand = random.nextInt(++count);
if (rand < num) {
list.set(rand, t);// 替换
}
}
}
public static void test(){
// for (int i = 0; i <10000; i++) {//进行一万次
final Pool<Integer> award = new Pool<Integer>(10);//100个人抽10个奖
for (int j = 0; j < 100000; j++) {//每次100000人抽奖
award.add(j);
}
List<Integer> list = award.getList();
System.out.println("1万人的中奖人名单："+list+"\n"+"参赛人数："+award.getCount());
// }
}
public static void main(String[] args) {
test();
}
}