-1 
int getnum50()
{ 
  Random rand = new Random(); 
  return (1+rand.nextInt(50)); 
}
  • getnum50()1 から 50 までの 1 つの乱数である整数を返すという名前の定義済み関数が与えられます。
  • この関数は何度でも呼び出すことができますが、この関数はリソースを大量に消費することに注意してください。
  • 他の乱数発生器は使用できません。の定義を変更することはできませんgetnum50()。

1 から 100 までの数字をランダムに出力します。(100個の乱数ではありません)

ノート：

  • 私。すべての数値は、正確に 1 回出力する必要があります。
  • ii. 数字のリストにパターンがあってはなりません。リストは完全にランダムである必要があります。つまり、すべての数字はどの場所にも同じ確率で表示されます。
  • iii. 1 から 50 までの乱数を取得するために getnum50() を何度でも呼び出すことができますが、コードを最適化するようにしてください。
  • iv。getnum50() 以外の乱数生成関数は使用できません。

正しい出力を示すコードをいくつか書きました。

import java.util.Random;

public class RandomInteger{

    int number[]=new int[100];//To store numbers in random order

    public RandomInteger(){
        int n[]=new int[100];//array to store which random numbers are generated
        int off[]={-1,0};//offset to add
        System.out.println("Length of array number100 is:"+number.length);
        System.out.println("Generating  random numbers in the range 1-100:");
        for(int n1=0;n1<number.length;n1++){
            int rnd=off[(getnum50()-1)/50]+(getnum50()*2);
            if(n[rnd-1] == 0){
                n[rnd-1]=1;//to indicate which random number is generated
                number[n1]=rnd;
                System.out.println(number[n1]+" ");
            }
        }
    }
    //end of constructor

    int getnum50(){  
        Random rand = new Random(); 
        return (1+rand.nextInt(50));      
    }

    public static void main(String args[]){
        RandomInteger m= new RandomInteger();
    }
    //end of main()
}
//end of class

そのラウンドでは受け入れられましたが、次のラウンドで面接担当者は、それgetnum50()はコストのかかる方法であり、最良のシナリオでも、生成される数値ごとに 2 回呼び出す必要があると私に言いました。つまり、1 ～ 100 の場合は 200 回です。最悪のシナリオでは、それは無限であり、平均的なケースでは数万です。彼は、平均的なケースを大幅に改善するためにコードを最適化するように私に依頼しました。答えられなかったので、質問に対する適切な答えを教えてください。上記のコードを最適化するにはどうすればよいですか??

4

5 に答える 5

2

愚かな最適化の 1 つは、ランダム化されたソースが 1 ～ 50 に制限されているため、2 つの配列位置を設定した方がよいことに気付くことです。

rand = getnum50();
n[rand] = 1;
n[rand+50] = 1;

nこれで、すべてのインデックスが単純に の 1/2 になるため、配列はわずかに「少ない」ランダムになりn+50ますが、少なくともビルド配列の構築時間を半分に短縮しました。

于 2013-07-19T18:36:54.210 に答える
0

メソッド getnum50() を 2 回呼び出す理由は、次の行のためです。

int rnd = off[(getnum50()-1)/50] + (getnum50()*2);

これは自明のようです。そして、あなたの最悪のシナリオが非常に悪い理由は、このブロックのためです:

if(n[rnd - 1] == 0){
    n[rnd - 1] = 1;          //to indicate which random number is generated
    number[n1] = rnd;
    System.out.println(number[n1] + " ");
}

運の悪さによっては、各値を取得するのに非常に長い時間がかかる場合があります。したがって、最良の場合、最初に発生する 2 つの getnum50() 呼び出しを行いますが、配列がいっぱいになると、その可能性はますます低くなります。100 個の数字の場合、最後の数字が最初に成功する確率は 1% で、失敗するたびに getnum50() をさらに 2 回呼び出します。

申し訳ありませんが、これは効率を改善する方法には答えていませんが、効率が懸念される理由を説明しています。それが役に立てば幸い。

于 2013-07-19T18:56:06.043 に答える
0

あなたの問題は、あなたがリストの最後に近づいている場合、残っているいくつかのスポットで数字を得るためにたくさんの乱数を生成しなければならないということです. 次のように、現在の回答にかなり適合するいくつかの方法を減らすことができます。

  while(n[rnd-1] == 1)
  {
    rnd++;
    rnd=end%101;
  }
  n[rnd-1]=1;//to indicate which random number is generated
  number[n1]=rnd;
  System.out.println(number[n1]+" ");

ただし、getnum50 が記述できる何よりも高価であると想定する場合は、リストの後半に入力するときに呼び出す getnum50 の数を減らすことができます。数値を見つけるたびに、検索スペースを 1 つ減らすことができます (非プリミティブを使用):

while(myArrayList.size()>1)
{
   int rnd=0;
   if(myArrayList.size()>50);
     rnd=((getnum50()-1)/50)+((getnum50()*2)%myArrayList.size())+1;
   else
     rnd=getnum50()%myArrayList.size()+1;
   System.out.println(rnd);
   myArrayList.remove(rnd);
}
System.out.println(myArrayList.get(rnd);
myArrayList.remove(rnd);

この例では、最高、平均、最低は 149 回の getnum50 呼び出しです。

于 2013-07-19T18:58:02.380 に答える