java - 一定時間で一意の乱数のリストを生成する

Question

1 から 1,000,000 までの範囲の乱数が 100 個必要です。番号は一意である必要があり、重複してはなりません。この質問に似ていますが、範囲が大きすぎて配列を作成できません。

これらの 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);
        }
    }
}