-
Notifications
You must be signed in to change notification settings - Fork 0
/
AliasMethodVose.cs
119 lines (103 loc) · 3.53 KB
/
AliasMethodVose.cs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
using System;
using System.Collections.Generic;
using System.Linq;
namespace JOS.WeightedResult
{
public class AliasMethodVose
{
private readonly Random _random;
private readonly List<long> _probabilities;
private readonly List<int> _alias;
private readonly long _probabilitySum;
private readonly bool _even;
public int Probabilities { get; }
public AliasMethodVose(IEnumerable<int> probabilities)
{
if (probabilities == null)
{
throw new ArgumentNullException(nameof(probabilities));
}
_probabilities = new List<long>();
_alias = new List<int>();
_probabilitySum = 0;
_random = new Random();
_even = false;
var tempProbabilities = probabilities.Select(p => (long)p).ToArray();
Probabilities = tempProbabilities.Length;
var maxProbability = -1L;
var minProbability = -1L;
foreach (var probability in tempProbabilities)
{
if (probability < 0)
{
throw new ArgumentException($"Probability must be equal to 0 or higher, was '{probability}'");
}
maxProbability = maxProbability < 0 || probability > maxProbability
? probability
: maxProbability;
minProbability = minProbability < 0 || probability < minProbability
? probability
: minProbability;
_probabilitySum += probability;
}
_even = maxProbability == minProbability;
if (_even)
{
return;
}
for (var i = 0; i < tempProbabilities.Length; i++)
{
tempProbabilities[i] *= Probabilities;
_alias.Add(0);
_probabilities.Add(0);
}
var small = new List<int>();
var large = new List<int>();
for (var i = 0; i < tempProbabilities.Length; i++)
{
if (tempProbabilities[i] < _probabilitySum)
{
small.Add(i);
}
else
{
large.Add(i);
}
}
while (small.Count > 0 && large.Count > 0)
{
var l = small[small.Count - 1];
small.RemoveAt(small.Count - 1);
var g = large[large.Count - 1];
large.RemoveAt(large.Count - 1);
_probabilities[l] = tempProbabilities[l];
_alias[l] = g;
var newProbability = tempProbabilities[g] + tempProbabilities[l] - _probabilitySum;
tempProbabilities[g] = newProbability;
if (newProbability < _probabilitySum)
{
small.Add(g);
}
else
{
large.Add(g);
}
}
foreach (var g in large)
{
_probabilities[g] = _probabilitySum;
}
foreach (var l in small)
{
_probabilities[l] = _probabilitySum;
}
}
public int NextValue()
{
var i = _random.Next(Probabilities);
return _even || _random.Next((int)_probabilitySum) < _probabilities[i]
? i
: _alias[i];
}
}
}