class WeighedDistribution

An infinite set composed of specified items. The higher the weight is assigned to an item in {#initialize}, the higher the probability of {#sample} returning that item.

Constants

ItemAndWeight

@!visibility private

ItemsAndWeightsSum

@!visibility private

Public Class Methods

new(items_and_weights) click to toggle source

@param [Enumerable<Array<(Object, Numeric)>>] items_and_weights @param [Random] random

# File lib/weighed_distribution.rb, line 12
def initialize(items_and_weights)
  items_and_weights = items_and_weights.
    map { |item, weight| ItemAndWeight.new(item, weight) }
  @interim_weights_sums_table = InterimWeightsSumsTable.new(
    # Group items by equal weight:
    #   {a, 10}, {b, 10}, {c, 10}, … → {[a, b, c], 30}, …
    items_and_weights.group_by(&:weight).map do |weight, items_and_weights|
      ItemsAndWeightsSum.new(
        items_and_weights.map(&:item),
        weight * items_and_weights.size
      )
    end.
    # Balance weights distribution.
    butterfly_sort_by(&:weights_sum).
    #
    map { |x| [x.items, x.weights_sum] }
  )
  @weights_sum = items_and_weights.map(&:weight).reduce(&:+)
end

Public Instance Methods

map(&f) click to toggle source

@yieldparam [Object] item @yieldreturn [Object] @return [WeighedDistribution] having all items passed through the block.

# File lib/weighed_distribution.rb, line 88
def map(&f)
  Mapped.new(self, &f)
end
sample(args = {}) click to toggle source

This method works for O(log(w)) where w is the number of distinct weights passed to {#initialize}.

@overload sample

@return [Object]

@overload sample(random: rng)

@param [Random] rng
@return [Object]
# File lib/weighed_distribution.rb, line 40
def sample(args = {})
  rng = args[:random] || Kernel
  #
  chosen_interim_weights_sum = rng.rand(@weights_sum)
  # Binary-search for @interim_weights_sums_table's entry index which is:
  #   chosen_interim_weights_sum ≥ (previous entry).interim_weights_sum and
  #   chosen_interim_weights_sum < (chosen entry).interim_weights_sum
  chosen_entry_index = begin
    table = @interim_weights_sums_table
    start_index = 0
    end_index = table.last_index
    while true
      middle_index = ((end_index + start_index) / 2).floor
      break middle_index if
        chosen_interim_weights_sum >= table[middle_index - 1].interim_weights_sum and
        chosen_interim_weights_sum < table[middle_index].interim_weights_sum
      if chosen_interim_weights_sum >= table[middle_index].interim_weights_sum then
        start_index = middle_index + 1
      else # if chosen_interim_weights_sum < table[middle_index].interim_weights_sum then
        end_index = (middle_index - 1).but_not_less_than(start_index)
      end
    end
  end
  #
  chosen_entry = @interim_weights_sums_table[chosen_entry_index]
  #
  chosen_item = begin
    chosen_items = chosen_entry.value
    if chosen_items.size == 1 then
      chosen_items.first
    else
      previous_entry = @interim_weights_sums_table[chosen_entry_index - 1]
      chosen_items_weights_sum = chosen_entry_weight =
        previous_entry.interim_weights_sum - chosen_entry.interim_weights_sum
      weight_per_item =
        chosen_items_weights_sum / chosen_items.size
      chosen_item_index =
        ((chosen_interim_weights_sum - previous_entry.interim_weights_sum) / weight_per_item).floor
      chosen_items[chosen_item_index]
    end
  end
  #
  return chosen_item
end