从数据流中等概率抽取一定的结果。
- 数据总量为n，需要取k个
- 构建一个k数组，前k个元素放入数组中
- 从第k+1个开始，k/i(i为当前的数量)的概率决定是否留在数组中，随机挑一个移出队列。
证明：
- 前k个数据。第k+1步被替换的概率：
$$
\frac{k}{k+1}\times \frac{1}{k}=\frac{1}{k+1}
$$
保留的概率:
$$
1-\frac{1}{k+1}=\frac{k}{k+1}
$$
一直到第n个，保留的概率：
$$
1\times \frac{k}{k+1}\times\frac{k+1}{k+2}\times\frac{k+2}{k+3}\times…\times\frac{n-1}{n}=\frac{k}{n}
$$
k后面的数据，i
被替换的概率：
$$
1-\frac{k}{i+1}\times\frac{1}{k}=\frac{i}{i+1}
$$
一直到最后一个：
$$
\frac{k}{i}\times\frac{i}{i+1}\times…\times\frac{n-1}{n}=\frac{k}{n}
$$1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22public class Sampling{
public static int[] sampling(int K, int N){
int[] arr = new int[N];
for(int i = 0; i < N; i++){
arr[i] = i;
}
int[] pool = new int[K];
for(int i = 0; i < K; i++){
pool[i] = arr[i];
}
Random random = new Random();
for(int i = K; i < N; i++){
int index = random.nextInt(i + 1);
if(index < K){
pool[index] = arr[i];
}
}
return pool;
}
}