有效选择随机数

Question

我有一个方法，它使用随机样本近似计算。这种方法被称为数百万次，所以选择随机数的过程非常重要。

我不知道Java类的速度有多快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

对于Mersenne Twister，您可以尝试使用existing Java implementation（or this one）。

记住最MT的是不加密安全。

Answer 2

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

Answer 3

永远猜不到，经常测量。

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

此外，你永远不应该依赖于已知的错误将不会发生，只是代码defensivley所以它不会。检测重复，如果重复，则不要添加它，并用continue语句跳过迭代。

至于最快的方法和随机数... 你不能在Java的Math.random()得到随机数。你只能得到伪随机数。你想要这样做的速度有多快会牺牲你看起来随机的表现。产生伪随机数最快的方法将涉及位移和基于种子值的加法，例如System.getCurrentMilliSeconds()。而且，伪随机数的产生已经非常快，因为它只是原始的CPU算术，所以你可能会一旦你看到用Math.random()产生一个毫秒就足够快乐了。

Answer 4

你可以使用线性同余随机发生器：http://en.wikipedia.org/wiki/Linear_congruential_generator [尚未考虑其统计缺点]

你只需要的（X + C）％M为每个数的计算。然而，根据我的经验，对象的创建（比如每次调用新的Set和添加，取决于您使用的实现）可能会比调用nextInt（）更快。也许你应该试试像例如这一个：http://www.eclipse.org/tptp/

Answer 5

我没有任何关于你的实际问题的任何意见，我不知道太多的Java（只是徘徊）。然而，在我看来，你正试图建立一个扑克手评估器，这个线程http://pokerai.org/pf3/viewtopic.php?f=3&t=16包含一些非常快速的Java手评估器。希望这些代码中的一些可能会有所帮助。

Answer 6

看起来你要选择一个ķ - combination从一组小号无需更换，具有ň不同的值，ķ = 5和ñ = 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 7

如果你被这样的事实，你必须跳过重复放缓，你可以通过创建所有的卡值的列表，然后从列表中删除的卡都选择解决这个问题并在下一次选择较小范围内的随机数。类似这样的：

// 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，所以你很少打一个副本，并且连续两次都是重复的概率很小。这一切都取决于需要多长时间才能生成一个随机数，而不是设置数组需要多长时间并执行删除操作。最简单的方法是做一些实验和测量。 （或简介！）

Answer 8

不要试图开发你已知的随机数发生器。使用已知的一个类似的SecureRandom替代：

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