Review of reservoir sampling

Question

I've been studying Reservoir sampling for a couple of days. What I've tried here is draw a uniformly random sample of size 3 from bigger data (the 26 characters of the English alphabet) via reservoir sampling. Below is what I've come up with.

If anyone could review my code and offer some suggestions, that'd be great.

import java.util.TreeMap;

public class test1 {
    public test1(){
        String[] data = "A B C D E F G H I J K L M O P".split(" ");
        double[] freq = new double[data.length];
        int k = 3;
        String[] sample = new String[k];

        // the tree map stores the count of appearance of each letter during
        // the total sampling procedure
        TreeMap<String, Double> dmap = new TreeMap<String, Double>();
        for (int index = 0; index < data.length; index++) {
            dmap.put(data[index], 0.0);
        }

        for (int loop = 0; loop < 1000000; loop++) {
            int i = 0;
            // initiate the sample
            while (i < k) {
                sample[i] = data[i++];
            }
            // start sampling from the reservoir
            for (; i < data.length; i++) {
                int r = (int) (Math.random() * (i + 1));
                if (r < k) {
                    sample[r] = data[i];
                }
            }
            // update the count of each entry in the map
            for (String s : sample) {
                dmap.put(s, dmap.get(s) + 1);
            }
        }
        int index = 0;
        for (Double s : dmap.values().toArray(new Double[dmap.size()])) {
            freq[index++] = s;
            // System.out.println(s);
        }
        // calculate statistics
        double mean, stddev , cov;
        mean = stats.mean(freq);
        stddev = stats.stddev(freq);
        cov = (stddev / mean) * 100;
        System.out.println(" mean                   : " + mean);
        System.out.println(" coeff of variation(%)  : " + cov);     }

    public static void main(String[] args) {
        new test1();
    }
}

Stats class:

final class stats {

    private stats() {}

    public static double sum(double[] a) {
        double sum = 0.0;
        for (int i = 0; i < a.length; i++) {
            sum += a[i];
        }
        return sum;
    }

    public static double mean(double[] a) {
        if (a.length == 0)
            return Double.NaN;
        double sum = sum(a);
        return (double) sum / a.length;
    }

    public static double stddev(double[] a) {
        return Math.sqrt(var(a));
    }

    public static double var(double[] a) {
        if (a.length == 0)
            return Double.NaN;
        double avg = mean(a);
        double sum = 0.0;
        for (int i = 0; i < a.length; i++) {
            sum += (a[i] - avg) * (a[i] - avg);
        }
        return sum / (a.length);
    }
}

My output:

 mean                   : 200000.0
 coeff of variation(%)  : 0.18734211130086761

Edit

I'v received some very helpful suggestions regarding the structure of the code . the generic version provided by 200_success was really a nice one. But some of the "procedural"-ness i feel that my code has , is mainly because the api for the actual code for which this was a test-case , demanded a static method which only read the input and gave a sample output. Hence to keep things visually similar , i tried putting them all in one method... The constructor ( not an ideal option many would rightly argue ).

Why the constructor? Well , it made me get away with just one small line in the main method. ( I was feeling pretty lazy back then .)

Edit 2 : Found out about R yesterday, after a little youtube-ing for for tutorials , made a few plots . Thought i'd upload a couple of them , just for fun. (and a better view of the data)

1. Box-plot of the number of times each letter of the alphabet(A-Z) had come up

2. Bar-plot of the same data

Answer 1

Functionally, your code is correct. My main criticisms are:

• Separation of concerns. You've lumped all of the functionality (except some basic math) into one function. (And it's a constructor!) You could, at the very least, split the code into
  • The reservoir sampling algorithm
  • Statistics gathering and calculation
  • Your test case. (By the way, you skipped "N" in your test case, probably unintentionally. No big deal.)
• Generality. It would be nice to write a reusable class that lets you reservoir-sample any pool of data, for any data type, for any k items. However, you've made two assumptions that prevent you from generalizing the code to handle any data type:
  • Your data are Comparable. A simple way to drop this requirement is to use a HashMap instead of a TreeMap.
  • Your data contain no repeats, or that repeated elements are indistinguishable. This is debatable; I've taken the view that if "A" appears in the data pool twice, you should be able to count the number of times the first "A" is selected separately from when the second "A" is selected.

With those ideas in mind, here's what I came up with:

import java.lang.reflect.Array;
import java.util.Random;

public class ReservoirSampler<T> {

    //////////////////////////////////////////////////////////////////

    class Stats {
        private int[] freq;

        private Stats(T[] pool) {
            this.freq = new int[pool.length];
        }

        private void collect(int[] rawSample) {
            for (int index : rawSample) {
                freq[index]++;
            }
        }

        public double mean() {
            if (0 == this.freq.length) {
                return Double.NaN;
            }
            double sum = 0;
            for (int f : this.freq) {
                sum += f;
            }
            return sum / this.freq.length;
        }

        public double var() {
            if (0 == this.freq.length) {
                return Double.NaN;
            }
            double avg = mean();
            double sum = 0;
            for (int f : this.freq) {
                sum += (f - avg) * (f - avg);
            }
            return sum / this.freq.length;
        }

        public double stddev() {
            return Math.sqrt(this.var());
        }
    }

    //////////////////////////////////////////////////////////////////

    private T[] pool;
    private Random random;
    public Stats stats;

    public ReservoirSampler(T[] pool) {
        this.pool = pool;
        this.random = new Random();
        this.stats = new Stats(pool);
    }

    /* Returns indexes of the k items selected from the pool */
    public int[] rawSample(int k) {
        int[] sample = new int[k];
        int i = 0;
        // Initialize the sample
        while (i < k) {
            sample[i] = i++;
        }
        // Sample from the reservoir
        for (; i < pool.length; i++) {
            int r = random.nextInt(i + 1);
            if (r < k) {
                sample[r] = i;
            }
        }
        this.stats.collect(sample);
        return sample;
    }

    /* Returns k items selected from the pool */
    public T[] reservoirSample(int k) {
        // We would prefer to say
        //   T[] sample = new T[k]
        // but T is unknown at runtime due to type erasure.
        Class c = this.pool.getClass().getComponentType();
        @SuppressWarnings({"unchecked"})
        T[] sample = (T[])Array.newInstance(c, k);

        int[] sampleIndexes = rawSample(k);
        for (int i = 0; i < k; i++) {
            sample[i] = this.pool[sampleIndexes[i]];
        }
        return sample;
    }

    public static void main(String[] args) {
        String[] alphabet = "A B C D E F G H I J K L M O P".split(" ");
        ReservoirSampler<String> rs = new ReservoirSampler<String>(alphabet);
        for (int loop = 0; loop < 1000000; loop++) {
            rs.reservoirSample(3);
        }
        double mean = rs.stats.mean();
        double stddev = rs.stats.stddev();
        System.out.println(" mean                  : " + mean);
        System.out.println(" coeff of variation(%) : " + 100 * stddev / mean);
    }
}

Answer 2

The algorithm itself looks solid, and your code looks good! I just wanted to provide some general style tips for Java.

First, why are you performing the core of your logic in the test1 constructor? That's highly irregular for Java. A constructor in general should only perform processing to initialize values unique to each instance of the class. It would be much more object-oriented to either move all that code directly into your main(String[] args) method or into a different static method. Having a test1 instance doesn't even make sense here.

Second (and much less importantly), you are breaking with several Java style conventions. I'm assuming you come from a Python background, because your code "feels" very Pythonic. That's not a bad thing, but they're two very different languages. Python attempts to always be short and to the point, while Java emphasizes verbosity and long, descriptive names for things. As such, here are a few tips to make your code more Java-esque (if you care):

• Class names should have each word capitalized, like in ThisTestClassName. So yours should be Test1 and Stats.
• Class names and variable names are also generally not abbreviated. So for example, your stats class would likely be called Statistics.
• Likewise, your method names would likely be renamed to something more descriptive. While anyone with a statistics background will know what you mean by stddev, it's standard for Java methods to be unabbreviated verb phrases. So it would be more appropriate to rename this method as getStandardDeviation(). Believe it or not, this really does make a difference in code readability. For example, when scanning your code, I was very confused by this line at first (Math.sqrt(var(a))) because it seemed like you were trying to do some odd JavaScript casting of a at a glance. A more descriptive method name like getVariation() would have easily avoided that confusion.
• To a lesser degree the "make things more descriptive" points from above apply to variable names as well, though it's much more common (if still frowned upon) to see this in local scope variables. For example, your code gets a little obfuscated in your test1() constructor because you use at least four variables which are only one letter: i, k, r, and s. In theory, with well-chosen variable names, I should be able to understand what the code is trying to do at any point without much surrounding context. That's the goal of making "self-documenting code".

And finally, one small tip which might clean up your code a little bit concerning this line:

for (Double s : dmap.values().toArray(new Double[dmap.size()]))

Here you can actually just use .toArray(new Double[0]) if you feel that would make your code less wordy. As you can see in the documentation, you don't actually have to pass in an array of the appropriate size to the toArray() method; it only uses your array for infer the type to return to you. So by just initializing an empty, zero-length array like this, you may be able to improve code readability a bit (and performance by just a small amount, by saving on memory allocation). There's no consensus or standard on this. Just personal preference.