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