java-蓄水池抽样-要求从N个元素中随机的抽取k个元素，其中N无法确定

蓄水池抽样（Reservoir Sampling）
相关证明可看这个链接：http://www.cnblogs.com/HappyAngel/archive/2011/02/07/1949762.html
以下为上面这个链接的两个截图：

import java.util.Arrays;
import java.util.Random;


public class ReservoirSampling {

	/**
	 * 题目：给定一个数据流，其中包含无穷尽的搜索关键字（比如，人们在谷歌搜索时不断输入的关键字）。
	 * 如何才能从这个无穷尽的流中随机的选取1000个关键字？
	 * Reservoir Sampling
	 * I read some proof on the internet,but I found they are hard to understand except this:
	 * http://www.cnblogs.com/HappyAngel/archive/2011/02/07/1949762.html
	 * It's excellent.
	 */
	public static void main(String[] args) {
		int k=100;
		int n=1000;
		int[] data=new int[n];
		for(int i=0;i<n;i++){
			data[i]=i;
		}
		int[] sample=reservoirSampling(data,k);
		System.out.println(Arrays.toString(sample));
	}
	
	public static int[] reservoirSampling(int[] data,int k){
		if(data==null){
			return new int[0];//In <Effective Java>,it advises to return int[0] instead of null.Am i doing right in this case?
		}
		if(data.length<k){
			return new int[0];
		}
		int[] sample=new int[k];
		int n=data.length;
		for(int i=0;i<n;i++){
			if(i<k){
				sample[i]=data[i];
			}else{
				int j=new Random().nextInt(i);
				if(j<k){
					sample[j]=data[i];
				}
			}
		}
		return sample;
	}

}

评论

1 楼 paul920531 2015-09-25  

39行有个bug:"int j=new Random().nextInt(i);" 改为"int j=new Random().nextInt(i+1);"