Class GuideTableDiscreteSampler
- java.lang.Object
-
- org.apache.commons.rng.sampling.distribution.GuideTableDiscreteSampler
-
- All Implemented Interfaces:
DiscreteSampler
,SharedStateDiscreteSampler
,SharedStateSampler<SharedStateDiscreteSampler>
public final class GuideTableDiscreteSampler extends java.lang.Object implements SharedStateDiscreteSampler
Compute a sample fromn
values each with an associated probability. If all unique items are assigned the same probability it is more efficient to use theDiscreteUniformSampler
.The cumulative probability distribution is searched using a guide table to set an initial start point. This implementation is based on:
Devroye, Luc (1986). Non-Uniform Random Variate Generation. New York: Springer-Verlag. Chapter 3.2.4 "The method of guide tables" p. 96.
The size of the guide table can be controlled using a parameter. A larger guide table will improve performance at the cost of storage space.
Sampling uses
UniformRandomProvider.nextDouble()
.- Since:
- 1.3
- See Also:
- Discrete probability distribution (Wikipedia)
-
-
Field Summary
Fields Modifier and Type Field Description private double[]
cumulativeProbabilities
The cumulative probability table (f(x)
).private static double
DEFAULT_ALPHA
The default value foralpha
.private int[]
guideTable
The inverse cumulative probability guide table.private UniformRandomProvider
rng
Underlying source of randomness.
-
Constructor Summary
Constructors Modifier Constructor Description private
GuideTableDiscreteSampler(UniformRandomProvider rng, double[] cumulativeProbabilities, int[] guideTable)
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description private static int
getGuideTableIndex(double p, int tableLength)
Gets the guide table index for the probability.static SharedStateDiscreteSampler
of(UniformRandomProvider rng, double[] probabilities)
Create a new sampler for an enumerated distribution using the givenprobabilities
.static SharedStateDiscreteSampler
of(UniformRandomProvider rng, double[] probabilities, double alpha)
Create a new sampler for an enumerated distribution using the givenprobabilities
.int
sample()
Creates anint
sample.java.lang.String
toString()
private static void
validateParameters(double[] probabilities, double alpha)
Validate the parameters.SharedStateDiscreteSampler
withUniformRandomProvider(UniformRandomProvider rng)
Create a new instance of the sampler with the same underlying state using the given uniform random provider as the source of randomness.-
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
-
Methods inherited from interface org.apache.commons.rng.sampling.distribution.DiscreteSampler
samples, samples
-
-
-
-
Field Detail
-
DEFAULT_ALPHA
private static final double DEFAULT_ALPHA
The default value foralpha
.- See Also:
- Constant Field Values
-
rng
private final UniformRandomProvider rng
Underlying source of randomness.
-
cumulativeProbabilities
private final double[] cumulativeProbabilities
The cumulative probability table (f(x)
).
-
guideTable
private final int[] guideTable
The inverse cumulative probability guide table. This is a guide map between the cumulative probability (f(x)) and the value x. It is used to set the initial point for search of the cumulative probability table.The index in the map is obtained using
p * map.length
wherep
is the known cumulative probabilityf(x)
or a uniform random deviateu
. The value stored at the index is valuex+1
whenp = f(x)
such that it is the exclusive upper bound on the sample valuex
for searching the cumulative probability tablef(x)
. The search of the cumulative probability is towards zero.
-
-
Constructor Detail
-
GuideTableDiscreteSampler
private GuideTableDiscreteSampler(UniformRandomProvider rng, double[] cumulativeProbabilities, int[] guideTable)
- Parameters:
rng
- Generator of uniformly distributed random numbers.cumulativeProbabilities
- The cumulative probability table (f(x)
).guideTable
- The inverse cumulative probability guide table.
-
-
Method Detail
-
sample
public int sample()
Creates anint
sample.- Specified by:
sample
in interfaceDiscreteSampler
- Returns:
- a sample.
-
toString
public java.lang.String toString()
- Overrides:
toString
in classjava.lang.Object
-
withUniformRandomProvider
public SharedStateDiscreteSampler withUniformRandomProvider(UniformRandomProvider rng)
Create a new instance of the sampler with the same underlying state using the given uniform random provider as the source of randomness.- Specified by:
withUniformRandomProvider
in interfaceSharedStateSampler<SharedStateDiscreteSampler>
- Parameters:
rng
- Generator of uniformly distributed random numbers.- Returns:
- the sampler
-
of
public static SharedStateDiscreteSampler of(UniformRandomProvider rng, double[] probabilities)
Create a new sampler for an enumerated distribution using the givenprobabilities
. The samples corresponding to each probability are assumed to be a natural sequence starting at zero.The size of the guide table is
probabilities.length
.- Parameters:
rng
- Generator of uniformly distributed random numbers.probabilities
- The probabilities.- Returns:
- the sampler
- Throws:
java.lang.IllegalArgumentException
- ifprobabilities
is null or empty, a probability is negative, infinite orNaN
, or the sum of all probabilities is not strictly positive.
-
of
public static SharedStateDiscreteSampler of(UniformRandomProvider rng, double[] probabilities, double alpha)
Create a new sampler for an enumerated distribution using the givenprobabilities
. The samples corresponding to each probability are assumed to be a natural sequence starting at zero.The size of the guide table is
alpha * probabilities.length
.- Parameters:
rng
- Generator of uniformly distributed random numbers.probabilities
- The probabilities.alpha
- The alpha factor used to set the guide table size.- Returns:
- the sampler
- Throws:
java.lang.IllegalArgumentException
- ifprobabilities
is null or empty, a probability is negative, infinite orNaN
, the sum of all probabilities is not strictly positive, oralpha
is not strictly positive.
-
validateParameters
private static void validateParameters(double[] probabilities, double alpha)
Validate the parameters.- Parameters:
probabilities
- The probabilities.alpha
- The alpha factor used to set the guide table size.- Throws:
java.lang.IllegalArgumentException
- ifprobabilities
is null or empty, oralpha
is not strictly positive.
-
getGuideTableIndex
private static int getGuideTableIndex(double p, int tableLength)
Gets the guide table index for the probability. This is obtained usingp * (tableLength - 1)
so is inside the length of the table.- Parameters:
p
- Cumulative probability.tableLength
- Table length.- Returns:
- the guide table index.
-
-