Package edu.uci.ics.jung.algorithms.util
Class WeightedChoice<T>
java.lang.Object
edu.uci.ics.jung.algorithms.util.WeightedChoice<T>
Selects items according to their probability in an arbitrary probability
distribution. The distribution is specified by a
Map
from
items (of type T
) to weights of type Number
, supplied
to the constructor; these weights are normalized internally to act as
probabilities.
This implementation selects items in O(1) time, and requires O(n) space.
-
Nested Class Summary
Nested ClassesModifier and TypeClassDescriptionprivate class
Manages light object/heavy object/light conditional probability tuples. -
Field Summary
FieldsModifier and TypeFieldDescriptionstatic final double
The default minimum value that is treated as a valid probability (as opposed to rounding error from floating-point operations).private List
<WeightedChoice<T>.ItemPair> private Random
-
Constructor Summary
ConstructorsConstructorDescriptionWeightedChoice
(Map<T, ? extends Number> item_weights) Equivalent tothis(item_weights, new Random(), DEFAULT_THRESHOLD)
.WeightedChoice
(Map<T, ? extends Number> item_weights, double threshold) Equivalent tothis(item_weights, new Random(), threshold)
.WeightedChoice
(Map<T, ? extends Number> item_weights, Random random) Equivalent tothis(item_weights, random, DEFAULT_THRESHOLD)
.WeightedChoice
(Map<T, ? extends Number> item_weights, Random random, double threshold) Creates an instance with the specified mapping from items to weights, random number generator, and threshold value. -
Method Summary
Modifier and TypeMethodDescriptionprivate void
enqueueItem
(T key, double value, double threshold, Queue<WeightedChoice<T>.ItemPair> light_weights, Queue<WeightedChoice<T>.ItemPair> heavy_weights) Adds key/value to the appropriate queue.nextItem()
Retrieves an item with probability proportional to its weight in theMap
provided in the input.void
setRandomSeed
(long seed)
-
Field Details
-
item_pairs
-
random
-
DEFAULT_THRESHOLD
public static final double DEFAULT_THRESHOLDThe default minimum value that is treated as a valid probability (as opposed to rounding error from floating-point operations).- See Also:
-
-
Constructor Details
-
WeightedChoice
Equivalent tothis(item_weights, new Random(), DEFAULT_THRESHOLD)
.- Parameters:
item_weights
- a map from items to their weights
-
WeightedChoice
Equivalent tothis(item_weights, new Random(), threshold)
.- Parameters:
item_weights
- a map from items to their weightsthreshold
- the minimum value that is treated as a probability (anything smaller will be considered equivalent to a floating-point rounding error)
-
WeightedChoice
Equivalent tothis(item_weights, random, DEFAULT_THRESHOLD)
.- Parameters:
item_weights
- a map from items to their weightsrandom
- the Random instance to use for selection
-
WeightedChoice
Creates an instance with the specified mapping from items to weights, random number generator, and threshold value.The mapping defines the weight for each item to be selected; this will be proportional to the probability of its selection.
The random number generator specifies the mechanism which will be used to provide uniform integer and double values.
The threshold indicates default minimum value that is treated as a valid probability (as opposed to rounding error from floating-point operations).
- Parameters:
item_weights
- a map from items to their weightsrandom
- the Random instance to use for selectionthreshold
- the minimum value that is treated as a probability (anything smaller will be considered equivalent to a floating-point rounding error)
-
-
Method Details
-
enqueueItem
private void enqueueItem(T key, double value, double threshold, Queue<WeightedChoice<T>.ItemPair> light_weights, Queue<WeightedChoice<T>.ItemPair> heavy_weights) Adds key/value to the appropriate queue. Keys with values less than the threshold get added tolight_weights
, all others get added toheavy_weights
. -
setRandomSeed
public void setRandomSeed(long seed) - Parameters:
seed
- the seed to be used by the internal random number generator
-
nextItem
Retrieves an item with probability proportional to its weight in theMap
provided in the input.- Returns:
- an item chosen randomly based on its specified weight
-