Reservoir sampling implementation. Reservoir sampling is a family of randomized algorithms for randomly choosing a sample of k items from a list S containing n items, where n is either a very large or unknown number. If question is unclear let me know I will reply asap. Looking for code review, optimizations and best practice.
public final class ReservoirSampling<T> {
private final int k;
/**
* Constructs ReservoirSampling object with the input sample size.
*
* @param k the number of sample elements needed.
* @throws IllegalArgumentException if k is not greater than 0.
*/
public ReservoirSampling(int k) {
if (k <= 0) {
throw new IllegalArgumentException("The k should be greater than zero");
}
this.k = k;
};
/**
* Returns a list of random `k` samples from the input list.
*
* @param list of elements from which we chose the k samples from.
* @return the list containing k samples, chosen randomly.
* @throws NullPointerException if the input list is null.
*/
public List<T> sample(List<T> list) {
final List<T> samples = new ArrayList<T>(k);
int count = 0;
final Random random = new Random();
for (T item : list) {
if (count < k) {
samples.add(item);
} else {
// http://en.wikipedia.org/wiki/Reservoir_sampling
// In effect, for all i, the ith element of S is chosen to be included in the reservoir with probability
// k/i.
int randomPos = random.nextInt(count);
if (randomPos < k) {
samples.set(randomPos, item);
}
}
count++;
}
return samples;
}
public static void main(String[] args) {
List<Integer> list = new ArrayList<Integer>();
list.add(1);
list.add(2);
list.add(3);
ReservoirSampling<Integer> reservoirSampling = new ReservoirSampling<Integer>(3);
System.out.print("Expected: 1 2 3, Actual: ");
for (Integer i : reservoirSampling.sample(list)) {
System.out.print(i + " ");
}
System.out.println();
System.out.print("Expected: random output: ");
list.add(4);
list.add(5);
list.add(6);
for (Integer i : reservoirSampling.sample(list)) {
System.out.print(i + " ");
}
}
}
