java - 在恒定时间内生成唯一随机数列表

Question

我需要从 1 到 1,000,000 范围内的 100 个随机数。编号必须唯一，不能重复。它类似于this question，但我的范围太大而无法从中创建数组。

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

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，没关系，但如果你将 100 提高到更高，则需要的时间会越来越长。

Answer 2

将您的范围分成 100 个部分，并从每个子范围中生成一个随机数。我认为它会在你的情况下正常工作。

或者，生成随机数并将它们放入 HashSet 中。当 HashSet 的大小为 100 时，你会中断。

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

Answer 3

在这里创建一个随机。

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

Answer 4

免责声明：此解决方案仅在可能生成的数字数量大大超过您必须生成的数字数量时才有效！

编辑：如果您愿意，您也可以将此确切代码与 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);
        }
    }
}