1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 package org.apache.hadoop.hbase.io.hfile;
18
19 import java.util.ArrayList;
20 import java.util.Arrays;
21 import java.util.Collections;
22 import java.util.Random;
23
24
25
26
27
28
29
30
31
32 public class RandomDistribution {
33
34
35
36 public interface DiscreteRNG {
37
38
39
40
41
42 int nextInt();
43 }
44
45
46
47
48 public static final class Flat implements DiscreteRNG {
49 private final Random random;
50 private final int min;
51 private final int max;
52
53
54
55
56
57
58
59
60
61
62
63
64
65 public Flat(Random random, int min, int max) {
66 if (min >= max) {
67 throw new IllegalArgumentException("Invalid range");
68 }
69 this.random = random;
70 this.min = min;
71 this.max = max;
72 }
73
74
75
76
77 @Override
78 public int nextInt() {
79 return random.nextInt(max - min) + min;
80 }
81 }
82
83
84
85
86
87
88
89 public static final class Zipf implements DiscreteRNG {
90 private static final double DEFAULT_EPSILON = 0.001;
91 private final Random random;
92 private final ArrayList<Integer> k;
93 private final ArrayList<Double> v;
94
95
96
97
98
99
100
101
102
103
104
105
106
107 public Zipf(Random r, int min, int max, double sigma) {
108 this(r, min, max, sigma, DEFAULT_EPSILON);
109 }
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125 public Zipf(Random r, int min, int max, double sigma, double epsilon) {
126 if ((max <= min) || (sigma <= 1) || (epsilon <= 0)
127 || (epsilon >= 0.5)) {
128 throw new IllegalArgumentException("Invalid arguments");
129 }
130 random = r;
131 k = new ArrayList<Integer>();
132 v = new ArrayList<Double>();
133
134 double sum = 0;
135 int last = -1;
136 for (int i = min; i < max; ++i) {
137 sum += Math.exp(-sigma * Math.log(i - min + 1));
138 if ((last == -1) || i * (1 - epsilon) > last) {
139 k.add(i);
140 v.add(sum);
141 last = i;
142 }
143 }
144
145 if (last != max - 1) {
146 k.add(max - 1);
147 v.add(sum);
148 }
149
150 v.set(v.size() - 1, 1.0);
151
152 for (int i = v.size() - 2; i >= 0; --i) {
153 v.set(i, v.get(i) / sum);
154 }
155 }
156
157
158
159
160 @Override
161 public int nextInt() {
162 double d = random.nextDouble();
163 int idx = Collections.binarySearch(v, d);
164
165 if (idx > 0) {
166 ++idx;
167 }
168 else {
169 idx = -(idx + 1);
170 }
171
172 if (idx >= v.size()) {
173 idx = v.size() - 1;
174 }
175
176 if (idx == 0) {
177 return k.get(0);
178 }
179
180 int ceiling = k.get(idx);
181 int lower = k.get(idx - 1);
182
183 return ceiling - random.nextInt(ceiling - lower);
184 }
185 }
186
187
188
189
190
191
192
193
194 public static final class Binomial implements DiscreteRNG {
195 private final Random random;
196 private final int min;
197 private final int n;
198 private final double[] v;
199
200 private static double select(int n, int k) {
201 double ret = 1.0;
202 for (int i = k + 1; i <= n; ++i) {
203 ret *= (double) i / (i - k);
204 }
205 return ret;
206 }
207
208 private static double power(double p, int k) {
209 return Math.exp(k * Math.log(p));
210 }
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226 public Binomial(Random random, int min, int max, double p) {
227 if (min >= max) {
228 throw new IllegalArgumentException("Invalid range");
229 }
230 this.random = random;
231 this.min = min;
232 this.n = max - min - 1;
233 if (n > 0) {
234 v = new double[n + 1];
235 double sum = 0.0;
236 for (int i = 0; i <= n; ++i) {
237 sum += select(n, i) * power(p, i) * power(1 - p, n - i);
238 v[i] = sum;
239 }
240 for (int i = 0; i <= n; ++i) {
241 v[i] /= sum;
242 }
243 }
244 else {
245 v = null;
246 }
247 }
248
249
250
251
252 @Override
253 public int nextInt() {
254 if (v == null) {
255 return min;
256 }
257 double d = random.nextDouble();
258 int idx = Arrays.binarySearch(v, d);
259 if (idx > 0) {
260 ++idx;
261 } else {
262 idx = -(idx + 1);
263 }
264
265 if (idx >= v.length) {
266 idx = v.length - 1;
267 }
268 return idx + min;
269 }
270 }
271 }