Class WeightedChoice<T>


  • public class WeightedChoice<T>
    extends java.lang.Object
    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 Classes 
      Modifier and Type Class Description
      private class  WeightedChoice.ItemPair
      Manages light object/heavy object/light conditional probability tuples.
    • Field Summary

      Fields 
      Modifier and Type Field Description
      static double DEFAULT_THRESHOLD
      The default minimum value that is treated as a valid probability (as opposed to rounding error from floating-point operations).
      private java.util.List<WeightedChoice.ItemPair> item_pairs  
      private java.util.Random random  
    • Constructor Summary

      Constructors 
      Constructor Description
      WeightedChoice​(java.util.Map<T,​? extends java.lang.Number> item_weights)
      Equivalent to this(item_weights, new Random(), DEFAULT_THRESHOLD).
      WeightedChoice​(java.util.Map<T,​? extends java.lang.Number> item_weights, double threshold)
      Equivalent to this(item_weights, new Random(), threshold).
      WeightedChoice​(java.util.Map<T,​? extends java.lang.Number> item_weights, java.util.Random random)
      Equivalent to this(item_weights, random, DEFAULT_THRESHOLD).
      WeightedChoice​(java.util.Map<T,​? extends java.lang.Number> item_weights, java.util.Random random, double threshold)
      Creates an instance with the specified mapping from items to weights, random number generator, and threshold value.
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      private void enqueueItem​(T key, double value, double threshold, java.util.Queue<WeightedChoice.ItemPair> light_weights, java.util.Queue<WeightedChoice.ItemPair> heavy_weights)
      Adds key/value to the appropriate queue.
      T nextItem()
      Retrieves an item with probability proportional to its weight in the Map provided in the input.
      void setRandomSeed​(long seed)  
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Field Detail

      • random

        private java.util.Random random
      • DEFAULT_THRESHOLD

        public static final double DEFAULT_THRESHOLD
        The default minimum value that is treated as a valid probability (as opposed to rounding error from floating-point operations).
        See Also:
        Constant Field Values
    • Constructor Detail

      • WeightedChoice

        public WeightedChoice​(java.util.Map<T,​? extends java.lang.Number> item_weights)
        Equivalent to this(item_weights, new Random(), DEFAULT_THRESHOLD).
        Parameters:
        item_weights - a map from items to their weights
      • WeightedChoice

        public WeightedChoice​(java.util.Map<T,​? extends java.lang.Number> item_weights,
                              double threshold)
        Equivalent to this(item_weights, new Random(), threshold).
        Parameters:
        item_weights - a map from items to their weights
        threshold - the minimum value that is treated as a probability (anything smaller will be considered equivalent to a floating-point rounding error)
      • WeightedChoice

        public WeightedChoice​(java.util.Map<T,​? extends java.lang.Number> item_weights,
                              java.util.Random random)
        Equivalent to this(item_weights, random, DEFAULT_THRESHOLD).
        Parameters:
        item_weights - a map from items to their weights
        random - the Random instance to use for selection
      • WeightedChoice

        public WeightedChoice​(java.util.Map<T,​? extends java.lang.Number> item_weights,
                              java.util.Random random,
                              double threshold)
        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 weights
        random - the Random instance to use for selection
        threshold - the minimum value that is treated as a probability (anything smaller will be considered equivalent to a floating-point rounding error)
    • Method Detail

      • enqueueItem

        private void enqueueItem​(T key,
                                 double value,
                                 double threshold,
                                 java.util.Queue<WeightedChoice.ItemPair> light_weights,
                                 java.util.Queue<WeightedChoice.ItemPair> heavy_weights)
        Adds key/value to the appropriate queue. Keys with values less than the threshold get added to light_weights, all others get added to heavy_weights.
      • setRandomSeed

        public void setRandomSeed​(long seed)
        Parameters:
        seed - the seed to be used by the internal random number generator
      • nextItem

        public T nextItem()
        Retrieves an item with probability proportional to its weight in the Map provided in the input.
        Returns:
        an item chosen randomly based on its specified weight