有效地选择随机数

Question

我有一个方法,它使用随机样本来近似计算.这种方法被称为数百万次,因此选择随机数的过程非常有效.

我不确定javas Random().nextInt真的有多快,但我的程序似乎并没有像我想的那样受益.

选择随机数时,我会执行以下操作(半伪代码):

// Repeat this 300000 times
Set set = new Set();
while(set.length != 5)
    set.add(randomNumber(MIN,MAX));

现在,这显然有一个糟糕的最坏情况运行时间,因为理论上的随机函数可以为永恒添加重复数字,从而永远保持在while循环中.但是,数字是从{0..45}中选择的,因此重复的值大部分都不太可能.

当我使用上面的方法时,它只比我的其他方法快40%,这不是近似的,但会产生正确的结果.这大约跑了100万次,所以我期待这种新方法至少快50%.

您对更快的方法有什么建议吗？或许你知道一种更有效的方法来生成一组随机数.

澄清一下,这是两种方法:

// 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++;
}

经过一些测试和分析,我发现这种方法最有效:

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);
}

Answer 1

您可以尝试将现有Java实现(或此实现)用于Mersenne Twister.

请记住,大多数MT 都不具有加密安全性.

Answer 2

看起来你想从一组S中选择一个没有替换的k - 组合,S有n个不同的值,k = 5和n = 52.你可以整个集合并选择k个元素(如@Tesserex建议的那样),或者k元素,同时避免重复(如你所示).您需要在特定环境和所选生成器中进行分析.我经常(但并非总是)看到适度的优势.shuffle()pick() pick()

private static final Random rnd = new Random();
private static final int N = 52;
private static final int K = 5;
private static final List<Integer> S = new ArrayList<Integer>(N);
static {
    for (int i = 0; i < N; i++) {
        S.add(i + 1);
    }
}
private final List<Integer> combination = new ArrayList<Integer>(K);

...

private void shuffle() {
    Collections.shuffle(S, rnd);
    combination.addAll(S.subList(0, K));
}

private void pick() {
    for (int i = 0; i < K; i++) {
        int v = 0;
        do {
            v = rnd.nextInt(N) + 1;
        } while (combination.contains(v));
        combination.add(v);
    }
}