Class: Vose::AliasMethod

Inherits:
Object
  • Object
show all
Defined in:
lib/vose.rb

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(probabilities) ⇒ AliasMethod

Returns a new instance of AliasMethod.

Raises:



9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
 
# File 'lib/vose.rb', line 9

def initialize(probabilities)
  raise InvalidArgumentException if probabilities.empty?
  raise InvalidArgumentException if probabilities.any?{|p| p < 0}

  @limit = probabilities.length
  sum = probabilities.reduce(:+)

  scale = @limit / sum.to_f
  scaled_probality = []
  probabilities.each do |p|
    scaled_probality << (p * scale)
  end

  @prob = Array.new(limit) { 0 }
  @alias = Array.new(limit) { 0 }

  preprocess(scaled_probality)
end

Instance Attribute Details

#limit ⇒ Object (readonly)

Returns the value of attribute limit.



7
8
9
 
# File 'lib/vose.rb', line 7

def limit
  @limit
end

Instance Method Details

#next ⇒ Object 



75
76
77
78
79
80
 
# File 'lib/vose.rb', line 75

def next
  fair_die_roll = @limit * rand
  i = fair_die_roll.floor
  p = fair_die_roll - i
  p <= @prob[i] ? i : @alias[i]
end

#preprocess(scaled_probality) ⇒ Object 



28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
 
# File 'lib/vose.rb', line 28

def preprocess(scaled_probality)
  small_worklist         = Array.new(limit) { 0 }
  large_worklist         = Array.new(limit) { 0 }
  small_worklist_counter = 0
  large_worklist_counter = 0

  0.upto(limit-1) do |j|
    if scaled_probality[j] > 1
      large_worklist[large_worklist_counter] = j
      large_worklist_counter+=1
    else
      small_worklist[small_worklist_counter] = j
      small_worklist_counter+=1
    end
  end

  while small_worklist_counter != 0 && large_worklist_counter != 0
    small_worklist_counter-=1
    large_worklist_counter-=1

    current_small_worklist_index = small_worklist[small_worklist_counter].to_i
    current_large_worklist_index = large_worklist[large_worklist_counter].to_i

    @prob[current_small_worklist_index] = scaled_probality[current_small_worklist_index]
    @alias[current_small_worklist_index] = current_large_worklist_index

    scaled_probality[current_large_worklist_index] = (scaled_probality[current_large_worklist_index] + scaled_probality[current_small_worklist_index]) - 1
    if scaled_probality[current_large_worklist_index] > 1
      large_worklist[large_worklist_counter] = current_large_worklist_index
      large_worklist_counter+=1
    else
      small_worklist[small_worklist_counter] = current_large_worklist_index
      small_worklist_counter+=1
    end
  end

  while small_worklist_counter != 0
    small_worklist_counter-=1
    @prob[small_worklist[small_worklist_counter]] = 1
  end

  while large_worklist_counter != 0
    large_worklist_counter-=1
    @prob[large_worklist[large_worklist_counter]] = 1
  end
end