0

重複の可能性：
Javaで一意の乱数を生成する

0から1000の間の乱数を生成し、0から1000の間で生成された一意の乱数を特定のメソッドに渡し続けるにはどうすればよいですか。そのために、0から1000までの数値を生成し、0から1000までの一意の乱数をリストに挿入して、生成している乱数がすでにリストに存在するかどうかを比較できるようにしました。存在する場合は、再度生成します。しかし、どういうわけか、以下のコードは時々失敗すると思います。

public class Testing4 {
    private static List<Integer> randomNumber;
    private static Random r = new Random();
    private static int rand;
    private static int endRange = 1000;

    public static void main(String args[]) throws IOException {

        randomNumber = new ArrayList<Integer>();

        for (int i = 1; i<= endRange; i++) {
            rand = r.nextInt(endRange);

            if(randomNumber.contains(rand)) {
                rand = r.nextInt(endRange);
            } else {
                randomNumber.add(rand);
            }

        // Pass the unique random number between 0 and 1000 to this method      
                randomNumberMethod(rand);

        }
    }
}
4

4 に答える 4

3

基本的に、0 から 1000 までの数字のリストをランダムな順序で生成しています。次の方法でこれをより効率的に達成できます。

public class Testing4 {
    private static List<Integer> randomNumber;
    private static int endRange = 1000;

    public static void main(String args[]) throws IOException {

        randomNumber = new ArrayList<Integer>(endRange);

        for (int i = 0; i<= endRange; i++) {                
            randomNumber.add(i);
        }

        Collections.shuffle(randomNumber);

        for (int i = 0; i<= endRange; i++) {                
            // Pass the unique random number between 0 and 1000 to this method      
            randomNumberMethod(randomNumber.get(i));
        }
    }
}

999 に到達するまでに何が起こっているかを考えてみてください。999 分の 1 の確率で、残りの利用可能な数を「推測」する可能性があります。

于 2012-05-21T21:45:50.367 に答える
2

0 から 1000 までの数値の一意のリストを生成するには、次の手順を実行します。

  • 0 から 1000 までのすべての数字を含むリストを作成する
  • Collections.shuffle() を使用してリストをシャッフルします
  • リストから必要な数だけ最初の数を取得します。

より複雑なアルゴリズムが必要な場合もありますが、可能な数の範囲と選択する必要があるアイテムの数が両方とも 1000 のオーダーである場合は、ランダムにシャッフルされたリストから最初のn数を取得するだけで十分です。すべての可能性の。

あなたが提案したようなことをしたい場合は、次のようにします。

  • 別のポスターが提案したように while ループを使用する
  • リストではなくセットを使用して、すでに選択されている値を保存します。

ただし、選択するアイテムの数が可能なアイテムの数に大きくなる傾向があるため、これは非効率的になります (たとえば、可能な 1000 から 10 の数字を選択している場合は問題ありません。900 を選択している場合)可能性のある 1000 のうち、以前に選択されていないものを見つける前に、毎回ますます多くの数字を拒否する必要があるため、非効率的になります)。

于 2012-05-21T21:40:12.210 に答える
1

コード検査から、このメソッドには動作を停止するものは何も表示されません。非常に非効率的です。

一つには、番号があなたが見たものであるかどうかをチェックすることはrandomNumber.contains(rand)、あなたがそれを行うたびに、リスト内のすべての番号と比較する必要があるため、生成する数が増えるほど時間がかかります。一致するものか、リスト内のすべての番号を試しました。これを行うためのより良い方法HashSetは、リストの代わりにを使用することです。これにより、リストに何を入れたかに関係なく、すべてのメンバーシップテストに同じ時間がかかります。

2 つ目の、より重要な最適化は、間違った質問をしている可能性があることに注意することで実行できます。一意の乱数を生成しようとしていますか、それとも 1 から endRange までのすべての数値をランダムな順序で生成しようとしていますか? すべての数字 (またはそれらの重要な部分) が必要な場合は、1 から 1000 までのすべての数字をリストに入れ、 を使用してそれらをシャッフルする方がはるかに高速Collections.shuffleです。したがって、生成コードは次のようになります。

java.util.List<Integer> nums = new java.util.ArrayList<Integer>(1001);
for (int i = 0; i <= 1000; i++)
{
   nums.add(new Integer(i));
}
java.util.Collections.shuffle(nums);
于 2012-05-21T21:55:48.663 に答える
0

ArrayList に既に存在する 2 つの数値が連続して生成されると、コードは失敗します。重複しているかどうかにかかわらず、2 番目の番号が使用されます。if ステートメントは、代わりに while ループにする必要があります (一意のステートメントが生成されるまで試行を続けるため)。

public class Testing4 {
    private static HashSet<Integer> randomNumber;
    private static Random r = new Random();
    private static int rand;
    private static int endRange = 1000;

    public static void main(String args[]) throws IOException {

        randomNumber = new HashSet<Integer>();

        for (int i = 1; i<= endRange; i++) {    
            do
            {
               rand = r.nextInt(endRange);
            }
            while(randomNumber.contains(rand));

            randomNumber.add(rand);

            // Pass the unique random number between 0 and 1000 to this method      
            randomNumberMethod(rand);

        }
    }
}

編集: コメントに従って、配列リストではなく do/while およびハッシュ データ構造を使用して、重複した検索を高速化する必要があります。最終的な編集は上記のコードにあります。

于 2012-05-21T21:37:51.790 に答える