1
\$\begingroup\$

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 + " ");
        }
    }
}
\$\endgroup\$
  • \$\begingroup\$ You could add some short description at the top of your post about what exactly "ReservoirSampling" is (and please don't just link to the wikipedia article, make life easier for us and describe it in your own words briefly) \$\endgroup\$ – Simon Forsberg Feb 4 '14 at 20:52
  • \$\begingroup\$ Added description, although I am not sure why link to wikipedia would be inconvenient. \$\endgroup\$ – JavaDeveloper Feb 4 '14 at 21:11
  • \$\begingroup\$ @JavaDeveloper: Unless a problem description from a 3rd party is too large to embed here, it's best to add it for convenience. \$\endgroup\$ – Jamal Feb 5 '14 at 0:19
  • \$\begingroup\$ noted. will do it \$\endgroup\$ – JavaDeveloper Feb 5 '14 at 0:29
  • \$\begingroup\$ @JavaDeveloper By writing your own explanation, it shows that you care about your question, which will make reviewers also care more about it. \$\endgroup\$ – Simon Forsberg Feb 5 '14 at 9:39
4
\$\begingroup\$

This is not an accurate implementation of the Reservoir Sampling algorithm.

The Reservoir Algorithm creates a reservoir of size k and fills it from the first k items from the source data.

It then iterates through the remaining source data, and selects a random value for each subsequent item in the data set. If the random value is within the limits of the Reservoir, then the item is placed in the reservoir at that point.

The issue you have is in your details.... Consider a source dataset of size 4 (values a,b, c, and d), and a reservoir of size 3.

There should be a 3-in-4 chance that the 4th item is sampled. Conversely, there should be a 1-in-4 chance that it is not sampled.

In your code, if we applied this example, k would be 3. You would create a reservoir of size 3, and you would fill it with the values a, b, and c.

At this point, you would loop again and your item would be 'd', your count would be 3, and we would enter the 'else' clause.

You then get your random number with the expression: int randomPos = random.nextInt(count);, or, effectively nextInt(3).

nextInt(3) will never return the value 3 since nextInt(int) is an exclusive-of-the-end-range function. As a result, it will always return one of 0, 1, or 2.

These values are all less than 3.

As a consequence, your algorithm will always include the k+1 element in your reservoir.

You need to change the way you generate your random number to be: nextInt(count + 1); Alternatively, you should increment your count before it is used to generate the random value.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.