# Review of reservoir sampling

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

• Nice R plots. R is really powerful for statistics like this. Good language choice for the use case. Sep 14 '13 at 2:57

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);
}
}

• Thanks a lot for your time to review and post a sample of improvement. will keep these in mind the next time i write a code. This time however , the actual code for which i wrote this , the api for it demanded a single static method for the random extraction and subsequent printout. Hence to keep things similar , i made it all a bit "procedural". Sep 5 '13 at 9:06
• You may have to code to an ugly API, but that shouldn't stop you from having pretty code behind it. Just plop the contents of my main() into your test1(). Sep 5 '13 at 9:14
• Thank you for the edit , and also for the code.. I'm learning a lot from it, Especially in the type-erasure part. Thanks a lot. Sep 5 '13 at 9:51
• About the type-erasure workaround… you don't have to pass the class explicitly. I've amended the code to use reflection to determine the array type. Sep 6 '13 at 7:13

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.

• thanks a lot for your time to review my code. 1st of all , regarding the structure of the code , its a partof an assignment where the api demands a static method for the sampling. so i kept the OO parts to a minimum. in my eclipse project , i generally have one or two such test classes , where i put random blocks of code and test it out. I agree i got a bit lazy there , and naming conventions should have been followed. regarding your point about .toArray(new Double[0]) , it appears that only dmap.values() would suffice. Noticed it after posting the code. Sep 4 '13 at 14:32
• regarding the pythonic part , thats good to hear, im planning to start learning python soon ;) unfortunately , i dont have enough rep to give an upvote. Sep 4 '13 at 14:38
• @SomjitNag Nice! Good luck with Python. It's a fun language, and it looks like you'll find it intuitive. And yeah, you're right about dmap.values(). Wasn't paying enough attention! :) Sep 4 '13 at 14:42
• thanks :) also , i should mention , that while making the code , i found the use of a treemap to be a waste. Mainly because i dont really need sorting to be done at every entry. I wanted to implement a HashMap , and sort it at the end. But everywhere i looked , people were suggesting TreeMaps. What do you say ? Sep 4 '13 at 14:45
• @SomjitNag Yeah, it all depends on what you care about. As far as ease of coding, the TreeMap is probably easier, but if you wanted to pick up a small performance gain, HashMap would be a better choice as you observed. Sep 4 '13 at 14:51