-
Notifications
You must be signed in to change notification settings - Fork 62
/
UniformDataGenerator.java
114 lines (105 loc) · 3.56 KB
/
UniformDataGenerator.java
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
/**
* This code is released under the
* Apache License Version 2.0 http://www.apache.org/licenses/.
*
* (c) Daniel Lemire, http://lemire.me/en/
*/
package me.lemire.integercompression.synth;
import java.util.Arrays;
import java.util.BitSet;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Random;
/**
* This class will generate "uniform" lists of random integers.
*
* @author Daniel Lemire
*/
public class UniformDataGenerator {
/**
* construct generator of random arrays.
*/
public UniformDataGenerator() {
this.rand = new Random();
}
/**
* @param seed
* random seed
*/
public UniformDataGenerator(final int seed) {
this.rand = new Random(seed);
}
/**
* generates randomly N distinct integers from 0 to Max.
*/
int[] generateUniformHash(int N, int Max) {
if (N > Max)
throw new RuntimeException("not possible");
int[] ans = new int[N];
HashSet<Integer> s = new HashSet<Integer>();
while (s.size() < N)
s.add(new Integer(this.rand.nextInt(Max)));
Iterator<Integer> i = s.iterator();
for (int k = 0; k < N; ++k)
ans[k] = i.next().intValue();
Arrays.sort(ans);
return ans;
}
/**
* output all integers from the range [0,Max) that are not in the array
*/
static int[] negate(int[] x, int Max) {
int[] ans = new int[Max - x.length];
int i = 0;
int c = 0;
for (int j = 0; j < x.length; ++j) {
int v = x[j];
for (; i < v; ++i)
ans[c++] = i;
++i;
}
while (c < ans.length)
ans[c++] = i++;
return ans;
}
/**
* generates randomly N distinct integers from 0 to Max.
*
* @param N
* number of integers to generate
* @param Max
* bound on the value of integers
* @return an array containing randomly selected integers
*/
public int[] generateUniform(int N, int Max) {
if (N * 2 > Max) {
return negate(generateUniform(Max - N, Max), Max);
}
if (2048 * N > Max)
return generateUniformBitmap(N, Max);
return generateUniformHash(N, Max);
}
/**
* generates randomly N distinct integers from 0 to Max.
*/
int[] generateUniformBitmap(int N, int Max) {
if (N > Max)
throw new RuntimeException("not possible");
int[] ans = new int[N];
BitSet bs = new BitSet(Max);
int cardinality = 0;
while (cardinality < N) {
int v = rand.nextInt(Max);
if (!bs.get(v)) {
bs.set(v);
cardinality++;
}
}
int pos = 0;
for (int i = bs.nextSetBit(0); i >= 0; i = bs.nextSetBit(i + 1)) {
ans[pos++] = i;
}
return ans;
}
Random rand = new Random();
}