有效地选择随机数

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 实现 (或这个）用于梅森旋转器。

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

Answer 2

您似乎想从一组中选择一个k-组合 S 无需替换，S 具有 n 个不同值，k = 5 且 n > = 52.您可以shuffle()整个集合并选择k个元素（如@Tesserex建议），或pick()k 个元素，同时避免重复（如您所示）。您需要在您的特定环境和您选择的生成器中进行分析。我经常（但并非总是）看到 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);
    }
}

Answer 3

一种常见的技术是从所有可能输入的列表开始，然后从中随机选择，然后删除。这样就不会有选择重复项并循环未知时间的风险。当然，这种方法仅适用于离散数据，但幸运的是整数可以。还要记住，如果可能的话，您的列表（或其他数据结构）选择和删除应该是 O(1)，因为您关注的是速度。

Answer 4

您可以使用线性同余作为随机生成器： http://en.wikipedia.org/wiki/Linear_congruential_generator< /a> [但考虑它们的统计缺点]

您只需要为每个数字计算 (x + c) % m 。然而，根据我的经验，创建对象（就像每次调用 new Set 和 add 时所做的那样，具体取决于您使用的实现）可能会比调用 nextInt() 花费更多的速度。也许您应该尝试像这样的探查器： http://www.eclipse.org/tptp/

Answer 5

我对你的实际问题没有任何意见，而且我对Java了解不多（只是闲逛）。然而，在我看来，您正在尝试为扑克构建一个手牌评估器，并且此线程 http://pokerai.org/pf3/viewtopic.php?f=3&t=16 包含一些极快的 Java 手牌评估器。希望其中一些代码可以有所帮助。

Answer 6

如果您因必须跳过重复项而减慢速度，则可以通过创建所有卡值的列表来解决该问题，然后在选择卡时从列表中删除并在一个随机数中选择一个随机数。下次范围较小。像这样：

// Assuming we're just numbering all the cards 0 to 51. This could be more sophisticated, of course.
ArrayList cards=new ArrayList(52);
for (int x=0;x<52;++x)
  cards=new Integer(x);

Integer[] hand=new Integer[5];
for (int h=0;h<5;++h)
{
  // Pick a card from those remaining
  int n=random.nextInt(cards.size());
  hand[h]=cards.get(n);
  // Remove the picked card from the list
  cards.remove(n);
}

对于第一次抽奖，cards.get(n) 将返回 n，无论 n 是什么。但从那时起，值将被删除，因此 cards.get(3) 可能会返回 7 等。

创建列表并从中删除会增加大量开销。我的猜测是，如果您一次只选取 5 张牌，则碰撞的概率足够小，因此在找到重复项后消除它们会比阻止它们更快。即使在最后一次抽奖中，重复的概率也仅为 4/52=1/13，因此您很少会抽到重复的结果，并且连续 2 次抽奖都是重复的概率也很小。这完全取决于生成随机数所需的时间与设置数组和执行删除所需的时间相比。最简单的判断方法是做一些实验和测量。 （或个人资料！）

Answer 7

永远不要猜测，总是测量。

 long time = System.getCurrentMilliseconds();
 Random().nextInt()
 System.out.println(System.getCurrentMilliseconds() - time);

另外，您永远不应该依赖于已知错误发生的频率，只需编写防御性代码，这样就不会发生。检测重复项，如果是重复项，则不添加它，并使用 continue 语句跳过迭代。

至于最快的方法和随机数......
您无法在 Java 的 Math.random() 中获取随机数。你只能得到伪随机数。你想要的速度有多快，是以牺牲你对它们出现的看似随机的程度为代价的。生成伪随机数的最快方法将涉及基于种子值的位移和加法，例如 System.getCurrentMilliSeconds() 此外，伪随机数生成已经相当快了，因为它是无论如何，这只是原始的 CPU 算术，所以当您看到使用 Math.random() 生成一个算术需要多少毫秒时，您可能会很高兴。

Answer 8

不要尝试开发您已知的随机数生成器。请改用 SecureRandom 等已知的扩展：

http://www.owasp.org/index.php/使用_the_Java_Cryptographic_Extensions