在常数时间内生成唯一随机数列表

Question

我需要从1到1,000,000的范围内获取100个随机数字，这些数字必须是唯一的，不能重复。 这与此问题类似，但我的范围太大了，无法创建数组。

我需要多次生成这100个随机数，因此生成速度需要尽可能快，最好是O(1)。有什么最快的方法吗？

- Tom

---

生成N个数字永远不会少于O(N)。 - Marko Topolnik

但是 OP 想要生成 100 个随机数，而不是任意数量的随机数。 - Miserable Variable

@MiserableVariable 如果你这么说，无论你做什么，它都将始终是O(1)。 - Marko Topolnik

Answer 1

我会使用一个HashSet和Mersenne Twister。

代码：

    MersenneTwisterFast ran = new MersenneTwisterFast();
    long time = System.nanoTime();
    Set set = new HashSet(100);
    while( set.size()<100) {
        set.add(ran.nextInt(1000000));
   }

System.out.println(System.nanoTime()-time+" : nano");
System.out.println(set.size());

输出结果为：

320000 : 纳秒

100

足够快吗？是的，这是O(1)，因为你总是处理100个数字。

要注意生日悖论，在这里你从1000000个数字中选择了100个，这很好，但如果你增加到更多，它会变得越来越慢。

- Frank

---

我使用Caliper进行确认，确实比Random（Lion，JSE 7）快两倍以上。 - Marko Topolnik

嗯...我现在扩展了我的测试，故事突然改变了。原始生成器（nextInt()）确实快了一倍，但是一旦你使用一个边界（nextInt(100)），差异就会消失为零。 - Marko Topolnik

@Frank：如果发生高碰撞会怎么样？似乎ran.nextInt()可能会被调用150次甚至更多。有没有限制？ - Yogendra Singh

请查看生日悖论，链接在我的回答中...但对于这个解决方案来说，这意味着它会变得很慢。 - Frank

工作得非常完美，速度也非常快。我以前从未听说过MT。谢谢。 - Tom

Answer 2

在这里创建一个随机数。

 Random generator = new Random();

创建一个计时器类，每 x 秒执行该函数。

 int d = 1000; //milliseconds 
 ActionListener t = new ActionListener() {
  public void actionPerformed(ActionEvent e) {
      //...Number genration task Here

  for (int idx = 1; idx <= 10; ++idx){
  int r = generator.nextInt(1000000);
  log("Generated : " + r);
  }
  }
  };
  new Timer(a,t).start()

- saum22

Answer 3

免责声明：此解决方案仅在可能生成的数字数量远远超过您需要生成的数字数量时才能快速工作！

编辑：如果您喜欢，也可以使用Mersenne Twister来运行此代码。

import java.util.HashSet;
import java.util.Iterator;
import java.util.Random;

public class MakeRand {
    private static final HashSet<Integer> theNumbers = new HashSet<Integer>();
    private static final Random myRandom = new Random();

    private static void addNumber() {
         int newNumber = -1;
         do {
            newNumber = myRandom.nextInt(1000000) + 1;
         } while(theNumbers.contains(newNumber));

         theNumbers.add(newNumber);
    }

    public static void populate(int howMany) {
        for (int i = 0; i < howMany; i++) {
            addNumber();
        }
    }

    public static void main(String args[]) {
        populate(100);

        Iterator<Integer> iter = theNumbers.iterator();
        while(iter.hasNext()) {
            Integer current = iter.next();
            System.out.println(current);
        }
    }
}

- durron597

Answer 4

将您的范围分成100个部分，并从每个子范围生成一个随机数。我认为这在您的情况下会很好用。

或者，生成随机数并将它们放入HashSet中。当HashSet的大小为100时，您就可以停止了。

虽然如果您想生成100个随机数，它总是会是O(1)。

- damned

---

这样做可以等距离排列数字，因此它们不是随机的！ - durron597