有效地选择随机数 [英] Choosing random numbers efficiently
问题描述
我有一个方法，它使用随机样本来近似计算。这种方法被称为数百万次，因此选择随机数的过程非常有效。
I have a method, which uses random samples to approximate a calculation. This method is called millions of times, so its very important that the process of choosing the random numbers is efficient.
我不确定javas有多快 Random（）。nextInt 确实如此，但我的程序看起来不像尽可能多地受益。
I'm not sure how fast javas Random().nextInt really are, but my program does not seem to benefit as much as I would like it too.
选择随机数时，我会执行以下操作（半伪代码）：
When choosing the random numbers, I do the following (in semi pseudo-code):
// Repeat this 300000 times
Set set = new Set();
while(set.length != 5)
set.add(randomNumber(MIN,MAX));
现在，这显然是一个糟糕的最坏情况运行时间，因为理论上的随机函数可以为永恒添加重复的数字，从而永远保持在while循环中。但是，这些数字是从{0..45}中选择的，所以重复的值大部分都不太可能。
Now, this obviously has a bad worst-case running time, as the random-function in theory can add duplicated numbers for an eternity, thus staying in the while-loop forever. However, the numbers are chosen from {0..45}, so a duplicated value is for the most part unlikely.
当我使用上述方法时，它只有40比我的其他方法快一个百分点，它不是近似值，但产生正确的结果。这大约跑了100万次，所以我期待这种新方法至少快50％。
When I use the above method, its only 40% faster than my other method, which does not approximate, but yields the correct result. This is ran ~ 1 million times, so I was expecting this new method to be at least 50% faster.
你对更快的方法有什么建议吗？或许你知道一种更有效的方法来生成一组随机数。
Do you have any suggestions for a faster method? Or maybe you know of a more efficient way of generation a set of random numbers.
为了澄清，这里有两种方法：
To clarify, here is the two methods:
// Run through all combinations (1 million). This takes 5 seconds
for(int c1 = 0; c1 < deck.length; c1++){
for(int c2 = c1+1; c2 < deck.length; c2++){
for(int c3 = c2+1; c3 < deck.length; c3++){
for(int c4 = c3+1; c4 < deck.length; c4++){
for(int c5 = c4+1; c5 < deck.length; c5++){
enumeration(hands, cards, deck, c1, c2, c3, c4, c5);
}
}
}
}
}
// Approximate (300000 combinations). This takes 3 seconds
Random rand = new Random();
HashSet<Integer> set = new HashSet<Integer>();
int[] numbers = new int[5];
while(enumerations < 300000){
set.clear();
while(set.size() != 5){
set.add(rand.nextInt(deck.length));
}
Iterator<Integer> i = set.iterator();
int n = 0;
while(i.hasNext()){
numbers[n] = i.next();
n++;
}
经过一些测试和分析后，我发现这种方法最有效：
After some testing and profiling, I found this method to be the most effective:
Random rand = new Random();
int[] numbers = new int[5];
ArrayList<Integer> list = new ArrayList<Integer>();
while(enumerations < 300000){
while(list.size() != 5) {
int i = rand.nextInt(deck.length);
if(!list.contains(i)) list.add(i);
}
int index = 0;
for(int i : list){ numbers[index] = i; index++; }
enumeration(hands, cards, deck,numbers);
}
推荐答案
您可以尝试使用< a href =http://www-stat.stanford.edu/~naras/programs/#mt =noreferrer>现有的Java实现（或者这一个） Mersenne Twister 。
You can try using an existing Java implementation (or this one) for a Mersenne Twister.
请记住最MT的不加密安全。
Keep in mind most MT's are not cryptographically secure.
这篇关于有效地选择随机数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
