net.sf.neem.impl
Class RandomSamples

java.lang.Object
  net.sf.neem.impl.RandomSamples

public class RandomSamples
extends java.lang.Object

Efficient computation of random samples from a small universe. This is used for gossiping.

Constructor Summary

RandomSamples()

Method Summary

static int[]	mkUniverse(int n) Initializes the universe for computing random samples.
static int	uniformSample(int n, int[] universe, java.util.Random rand) Efficiently calculate a random sample.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

RandomSamples

public RandomSamples()

Method Detail

uniformSample

public static int uniformSample(int n,
                                int[] universe,
                                java.util.Random rand)

Efficiently calculate a random sample. This works by shuffling the array such that the first n elements, i.e. from universe[0] to universe[n-1] are an uniform random sample. This is true even if the same universe is used repeatedly without being reinitialized. Usually, the result is used as indexes in some ordered collection, which is the true universe. This is efficient, as it is O(n), for small samples and O(universe.length-n) for large samples.

Parameters:

n - size of sample.

universe - universe to draw from.

rand - random generator.

mkUniverse

public static int[] mkUniverse(int n)

Initializes the universe for computing random samples. This generates an integers array that can be used to compute random samples.

Parameters:

n - size of the universe