java 有效地选择随机数

Choosing random numbers efficiently

提问by Frederik Wordenskjold

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.

我有一种方法，它使用随机样本来近似计算。这种方法被调用了数百万次，因此选择随机数的过程是否有效是非常重要的。

I'm not sure how fast javas Random().nextIntreally are, but my program does not seem to benefit as much as I would like it too.

我不确定 java 的速度到底有多快Random().nextInt，但我的程序似乎并没有像我希望的那样受益。

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

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.

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

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.

当我使用上述方法时，它仅比我的其他方法快 40%，该方法不近似，但会产生正确的结果。这运行了大约 100 万次，所以我期望这种新方法至少快 50%。

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

采纳答案by Yuval Adam

You can try using an existing Java implementation(or this one) for a Mersenne Twister.

您可以尝试为Mersenne Twister使用现有的 Java 实现（或这个实现）。

Keep in mind most MT's are notcryptographically secure.

请记住，大多数 MT都不是加密安全的。

回答by trashgod

It looks like you want to select a k-combinationfrom a set Swithout replacement, with Shaving ndistinct values, k= 5 and n= 52. You can shuffle()the entire set and select kelements (as @Tesserex suggests), or pick()kelements while avoiding duplicates (as you've shown). You'll want to profile both in your particular environment and for your chosen generator. I often, but not always, see a modest edge for pick().

看起来你想从一个没有替换的集合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);
    }
}

回答by Searles

You could use linear congruence as a random generator: http://en.wikipedia.org/wiki/Linear_congruential_generator[yet consider their statistical disadvantages]

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

You only need a calculation of (x + c) % m for each number. Yet, in my experience the creation of objects (like you might do with every call of new Set and add, depending on which implementation you use) might cost you more speed than a call to nextInt(). Maybe you should try a profiler like e.g. this one: http://www.eclipse.org/tptp/

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

回答by Tesserex

A common technique is to start with a list of all the possible inputs, and randomly select from that, deleting ones as you go. That way there's no risk of selecting a duplicate and having to loop for an unknown amount of time. Of course this method only works with discrete data, but fortunately integers are. Also remember that your list (or other data structure) selection and deletion should be O(1) if possible, since you're focusing on speed.

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

回答by RD.

I don't have any input on your actual problem, and I don't know too much Java (just poking around). However it seems to me that you are trying to build a hand evaluator for poker and this thread http://pokerai.org/pf3/viewtopic.php?f=3&t=16contains some extremely fast java hand evaluators. Hopefully some of this code could be of help.

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

回答by Jay

If you're being slowed down by the fact that you have to skip over duplicates, you could solve that problem by creating a list of all the card values, and then removing from the list as cards are selected and choosing a random number in a smaller range the next time. Something like this:

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

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

For the first draw, cards.get(n) will return n, no matter what n is. But from then on, values will be removed so cards.get(3) might return 7, etc.

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

Creating the list and removing from it adds a bunch of overhead. My guess would be that if you're only picking 5 cards at a time, the probabilty of collisions is small enough that eliminating duplices after you find them would be faster than preventing them. Even on the last draw, the probability of a duplicate is only 4/52=1/13, so you'd rarely hit a duplicate at all and the probability that 2 draws in a row would both be duplicates would be tiny. It all depends on how long it takes to generate a random number compared to how long it takes to set up the array and do the removes. The easiest way to tell would be to do some experiments and measure. (Or profile!)

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

回答by Raj Kaimal

Don't try to develop your known random num generator. Use a known one like SecureRandom instead:

不要尝试开发您已知的随机数生成器。改用像 SecureRandom 这样的已知方法：

http://www.owasp.org/index.php/Using_the_Java_Cryptographic_Extensions

http://www.owasp.org/index.php/Using_the_Java_Cryptographic_Extensions

回答by Zombies

Never guess, always measure.

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

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

Also, you should never rely on how infrequent a known bug will happen, just code defensivley so it doesn't. Detect a duplicate, and if it is a duplicate then don't add it, and skip the iteration with a continuestatement.

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

As for fastest methods and random numbers... You can't get random numbers in Java's Math.random(). You can only get pseudo random numbers. How fast you want this to be comes at the sacrifice of how seemingly random you need to them appear. The fastest way to generate a pseudo-random number would involve bit shifting and addition based on the a seed value such as System.getCurrentMilliSeconds()Also, pseudo-random number generation is already pretty fast since it is just raw CPU arithmetic anyway, so you will probably be happy enough once you see how many milliseconds it takes to generate one with Math.random().

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