有效地选择随机数
我有一个方法，它使用随机样本来近似计算。 这种方法被称为数百万次，因此选择随机数的过程非常有效。
我不确定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 set = new HashSet(); int[] numbers = new int[5]; while(enumerations < 300000){ set.clear(); while(set.size() != 5){ set.add(rand.nextInt(deck.length)); } Iterator i = set.iterator(); int n = 0; while(i.hasNext()){ numbers[n] = i.next(); n++; }
经过一些测试和分析，我发现这种方法最有效：
Random rand = new Random(); int[] numbers = new int[5]; ArrayList list = new ArrayList(); 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); }
您可以尝试将现有Java实现 （ 或此 实现 ）用于Mersenne Twister 。
请记住，大多数MT 都不具有加密安全性。
看起来你想从一个S组中选择一个没有替换的k – 组合 ， S有n个不同的值， k = 5和n = 52.你可以shuffle()抽取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 S = new ArrayList (N); static { for (int i = 0; i < N; i++) { S.add(i + 1); } } private final List combination = new ArrayList (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); } }
一种常见的技术是从所有可能输入的列表开始，并从中随机选择，随时删除。 这样就没有选择复制品并且不得不循环一段未知时间的风险。 当然这种方法只适用于离散数据，但幸运的是整数。 还要记住，如果可能，您的列表（或其他数据结构）选择和删除应该是O（1），因为您专注于速度。
你可以使用线性同余作为随机生成器： http ： //en.wikipedia.org/wiki/Linear_congruential_generator [但考虑它们的统计缺点]
您只需要为每个数字计算（x + c）％m。 然而，根据我的经验，对象的创建（就像你可能每次调用新的Set和添加一样，取决于你使用的实现）可能比调用nextInt（）更快。 也许你应该尝试像这样的探查器： http ： //www.eclipse.org/tptp/
我对你的实际问题没有任何意见，我不太了解Java（只是四处寻找）。 然而，在我看来，你正在尝试为扑克建立一个手动评估器，这个线程http://pokerai.org/pf3/viewtopic.php?f=3&t=16包含一些非常快速的java手评估器。 希望这些代码中的一些可能会有所帮助。
如果你因为必须跳过重复项而放慢速度，你可以通过创建所有卡值的列表来解决这个问题，然后在选择卡片时从列表中删除并选择一个随机数。下次更小的范围。 像这样的东西：
// 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次抽取的概率都很小。 这一切都取决于生成随机数所需的时间与设置数组和执行删除所需的时间相比。 最简单的方法是做一些实验和测量。 （或者个人资料！）
从不猜测，总是测量。
long time = System.getCurrentMilliseconds(); Random().nextInt() System.out.println(System.getCurrentMilliseconds() - time);
此外，你永远不应该依赖已知错误发生的频率，只需要代码defensivley就可以了。 检测重复项，如果它是重复项，则不要添加它，并使用continue语句跳过迭代。
至于最快的方法和随机数…你不能在Java的Math.random()获得随机数。 您只能获得伪随机数。 你想要的速度有多快，牺牲了你需要看起来随机的样子。 生成伪随机数的最快方法是根据种子值（如System.getCurrentMilliSeconds()位移和加法。此外，伪随机数生成已经相当快，因为它无论如何都只是原始CPU算术，所以一旦你看到用Math.random()生成一个毫秒，你可能会很高兴。
不要尝试开发已知的随机数生成器。 使用像SecureRandom这样的已知代码：
http://www.owasp.org/index.php/Using_the_Java_Cryptographic_Extensions