6

最近のインタビューで、次の質問をされました。

getrnd50()1から 50 までの乱数を生成する指定されたメソッドを使用して、1 から 100 までの乱数を出力します。各乱数は、ランダムな順序で 1 回だけ印刷する必要があります。他の乱数発生器の使用は許可されておらず、 i は の定義を変更することを許可されていませんでした getrnd50()

正しい出力を与える次のコードを思いつきました。

import java.util.Random;

public class Test {

public static void main(String[] args) {
    int[] rs = new int[100];
    int count = 0;
    int k;
    while (count != 100) {

        // I decided to simply multiply the result of `getrnd50()` by 2. 
        // But since that would generate only even numbers,

        k = getrnd50() * 2;

        // I decided to randomly subtract 1 from the numbers. 
        // Which i accomlished as follows.          

        if (getrnd50() <= 25) // 25 is to half the possibilities.
            k--;

        // Every number is to be stored in its own unique location 
        // in the array `rs`, the location is `(number-1)`. 
        // Every time a number is generated it is checked whether it has 
        // already been generated. If not, it is saved in its position, printed and 
        // `count` is incremented.

        if (rs[k-1] == 0) {
            rs[k-1] = k;
            count++;
            System.out.print(k + " ");
        }
    }
}
// This is the method and i am not supposed to touch it.
static int getrnd50() {
    Random rand = new Random();
    return (1 + rand.nextInt(50));
}

}

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

私がそれを行うことができないことを表明したとき、彼は私にヒントを与えました.

新しい数を生成する際に、生成される数の数を考慮する。例のために。count99 になった場合、電話する必要はありませんgetrnd50()。残りの番号を見つけて印刷するだけです。

私は彼のドリフトを理解していましたが、それがどのように役立つかわからなかったので、明らかに拒否されました. 今、私は答えを知りたいと思っています。助けて!事前にサンクス!

注:数値生成の部分を指摘するだけで長いコードを書くのが面倒だと感じている人がいる場合、残りは簡単です。また、ヒントに従う義務はありません。

4

7 に答える 7

6

重要なのは、以前に番号を生成したかどうかを確認することです。これは、残りの番号を 1 つだけ探すと非常にコストがかかりますが、1 から 100 までの番号を順番に生成してシャッフルします。

コードでは、100 個の数字のうち 99 個を生成すると、残りの 1 個の数字が見つかるまで、乱数を生成してループします。それが、あなたのバージョンの平均的なケースが非常に悪い理由です。

代わりに配列をシャッフルするだけの場合は、シャッフル操作と同じ数の乱数だけが必要であり、数値出力が必要な数のシャッフル操作だけが必要です。

(シャッフルの詳細については、Fisher-Yatesシャッフル、特にシャッフルされた配列をその場で生成できる裏返しのバリアントを調べてください)

乱数を生成するには、固定の 1 ~ 50 のジェネレーターではなく、変数のジェネレーターが必要です。さまざまな方法でこれにアプローチできますが、可能な状態全体で出力を適切に分散させたい場合は、結果に偏りが生じないように十分注意してください。

たとえば、モジュロを使用しようとするのではなく、整数のビット数をシフトして使用することをお勧めします。値が目的の範囲外にある場合、これにはある程度のループが含まれますが、元の乱数生成を変更することができなければ、あなたの手は幾分拘束されます.

static int bits = 0;
static int r100 = 0;

static int randomInt(int range)
{
    int ret;

    int bitsneeded = 32 - Integer.numberOfLeadingZeros(range - 1);

    do {
            while(bits < bitsneeded)
            {
                    int r = (getrnd50()-1) * 50 + getrnd50()-1;
                    if(r < 2048)
                    {
                            r100 <<= 11;
                            r100 |= r;
                            bits += 11;
                    }
            }
            ret = r100 & ((1 << bitsneeded) - 1);
            bits -= bitsneeded;
            r100 >>=  bitsneeded;
    } while(ret >= range); 

        return ret + 1;
}

この実装では、100 個の値がシャッフルされた配列に対して 150 個の乱数の領域で何かを使用します。これは、モジュロ バージョンよりも悪いですが、元のバージョンの最良のケースであった入力範囲の 2 倍よりはましです。ランダム生成が本当にランダムである場合、無限の最悪のシナリオがまだありますが、ランダム生成は通常そのようには機能しません。もしそうなら、制約を考えると、歪みのない結果が現実的かどうかはわかりません。

説明のために、結果が微妙なので、これは私が提案したランダム ルーチンとモジュロ バージョンのグラフです。

乱数発生器のグラフ

要約すると、あなたの乱数生成は少し非効率的であり、改善の余地があると思いますが、インタビュアーが求めていた本当に大きな勝利は、最初からそれほど多くの乱数を必要としないことです。ますます減少する確率で検索を繰り返します。

于 2013-01-02T14:54:26.303 に答える
3

これがあなたがそれに答える方法です。それは、

  • シャッフルを使用して「カード」の O(n) スワッピングを取得すると仮定すると、モジュラスはシャッフルで減少します。つまりint[]、すべての値から始めて、Collections.shuffle() のようにシャッフルします。
  • getrnd50() を 2 回呼び出した場合、特にスワップする値が 50 個未満の場合は、必要以上にランダム性が高くなります。

編集:シャッフルの仕組みに慣れていない人のために、シャッフルのコードを追加しました

import java.util.*;
import java.lang.*;

class Main {
    public static void main(String... args) {
        int samples = 100;

        // all the numbers [1, 100]
        int[] nums = new int[samples];
        for (int i = 0; i < samples; i++) nums[i] = i + 1;

        for (int i = samples - 1; i > 0; i--) {
            int swapWith = nextInt(i + 1);

            // swap nums[i] and nums[swapWith]
            if (swapWith == i) continue;
            int tmp = nums[swapWith];
            nums[swapWith] = nums[i];
            nums[i] = tmp;
        }
        System.out.println("calls/sample " + (double) calls / samples);
        System.out.println(Arrays.toString(nums));

        int[] count49 = new int[49];
        for (int i = 0; i < 49 * 10000; i++)
            count49[nextInt(49) - 1]++;
        int[] count54 = new int[54];
        for (int i = 0; i < 54 * 10000; i++)
            count54[nextInt(54) - 1]++;
        System.out.println("Histogram check (49): " + Arrays.toString(count49));
        System.out.println("Histogram check (54): " + Arrays.toString(count54));

    }

    // keep track of the range of values.
    static int maxRandom = 1;
    // some random value [0, maxRandom)
    static int rand100 = 0;

    static int nextInt(int n) {
        while (maxRandom < 10 * n * n) {
            maxRandom *= 50;
            rand100 = rand100 * 50 + getrnd50() - 1;
        }
        int ret = rand100 % n;
        maxRandom = (maxRandom + n - 1) / n;
        rand100 /= n;
        return ret + 1;
    }

    static final Random rand = new Random();
    static int calls = 0;

    static int getrnd50() {
        calls++;
        return (1 + rand.nextInt(50));
    }
}

版画

コール/サンプル 0.94

[1, 37, 4, 98, 76, 53, 26, 55, 9, 78, 57, 58, 47, 12, 44, 25, 82, 2, 42, 30, 88, 81, 64, 99, 16 , 28, 34, 29, 51, 36, 13, 94, 80, 66, 19, 38, 20, 8, 40, 89, 72, 56, 75, 96, 35, 100, 95, 17, 74, 69 , 11, 31, 86, 92, 6, 27, 22, 70, 63, 32, 93, 84, 71, 15, 23, 5, 14, 62, 49, 43, 87, 65, 83, 33, 45 , 52, 39, 91, 60, 73, 68, 24, 97, 46, 50, 18, 79, 48, 77, 67, 59, 10, 7, 54, 90, 85, 21, 61, 41, 3 ]

ヒストグラムチェック(49):[10117、10158、10059、10188、10338、9959、10313、10278、10166、9828、10105、10159、10250、10152、9949、9855、10026、10040、9982、10112、100821、100821、10082 、10029、10052、9996、10057、9849、9990、9914、9835、10029、9738、9953、9828、9896、9931、9995、10034、10067、9745、9873、9903、9913、9913、9841、9823、9823、9823、9823、9823 、10007、9765]

ヒストグラムチェック(54):[10124、10251、10071、10020、10196、10170、10123、10096、9966、10225、10262、10036、10029、9862、9994、9960、10070、10127、10021、10166、10077、9983、9983 、10118、10163、9986、9988、10008、9965、9967、9950、9965、9870、10172、9952、9972、9828、9754、10152、9943、9996、9779、10014、937、9937、9937、9937、9937、9937 、9894、9803、9904、9915、9927、10000、9838]

この場合、100 個の番号に必要な getrnd50 の呼び出しは 100 回未満です。

シャッフルする値が 1000 個ある場合

calls/sample 1.509
于 2013-01-02T15:15:21.293 に答える
3

100 / 50 は整数なので、これは非常に簡単です。50 / (100 / 50) は整数なので、さらに簡単です。

よくわからない場合は、サンプル コードを次に示します。

int rnd1 = getrnd50();
int rnd2 = getrnd50();
if (rnd1 % 2 == 0)
{
    rnd2 += 50;
}
return rnd2;

概要は次のとおりです。

  • aおよびbと呼ばれる、1 から 50 の間でランダムに選択された 2 つの数値。
  • aが偶数の場合、 bに 50 を加算します。
  • bを返します。

必要に応じて、これをワンライナーにすることができます。

return getrnd50() + getrnd50() % 2 * 50;

ちょっとわかりにくすぎるけど。

編集:質問は、ランダムな整数のシーケンスではなく、シャッフルされたリストを実際に求めていたようです。

これは、1 から 100 までのリストを作成し、Fisher-Yates シャッフルのように 100 回のランダム スワップを行うことで実行できます。Fisher-Yates シャッフルでは、呼び出しの絶対最小数は 93 (式 で与えられるceil(log50(100!))) であると想像しますが、はるかに単純なアルゴリズムでは 200 を使用できます。

単純なアルゴリズムでは、100 個の要素のそれぞれを 100 個のランダムな要素と交換する必要があります。選択する数は、上記のジェネレーターで 1 ~ 100 から生成されます。

例えば:

for (int i = 0; i < 100; i++)
{
    swap(i, getrnd100() - 1); // - 1 for zero base!
}

完全なコードを次に示します。

int[] result = new int[100];
for (int i = 0; i < 100; i++)
{
    result[i] = i + 1;
}
for (int i = 0; i < 100; i++)
{
    int j = (getrnd50() + getrnd50() % 2 * 50) - 1;
    int tmp = result[i];
    result[i] = result[j];
    result[j] = tmp;
}
return result;

(免責事項: 私は Java を知りません。また、テストもしていません。)

最良の場合 200、最悪の場合 200、平均的な場合 200。

于 2013-01-02T14:54:24.987 に答える
0

(1){1、...、100}で初期化された配列Aを作成します。この配列の可変の「長さ」を保持します。

(2)1から長さまでの数をランダムに生成するランダムメソッドを作成します。このメソッドを呼び出すたびに、getrnd50()が2回以内に呼び出されます。戻り値を「index」として呼び出します。

(3)A [index]を出力し、A[length]をA[index]にスワップし、length--。

(4)配列が空になるまで、(1)〜(3)を繰り返します。

于 2013-01-02T15:19:46.193 に答える
0

さて、乱数ジェネレーターによって生成されることなく、n個の数字の最後の欠落した数のセットを印刷することができますか?

もしそうなら、再帰を利用して、呼び出しごとにセットのサイズを小さくして、n = 2になるまで、そしてgetrnd50()を1回呼び出すことができます。再帰的に戻るときは、各セットに欠落している番号を印刷するだけです。

于 2013-01-02T15:01:39.127 に答える
0
 List<Integer> lint ; 

  public void init(){
      random = new Random();
      lint = new LinkedList<>();
      for(int i = 1 ; i < 101; ++i) {
          lint.add(i); // for truly random results, this needs to be randomized.
      }
  }

  Random random ; 
  public int getRnd50() {
      return random.nextInt(50) + 1;
  }

  public int getRnd100(){

      int value = 0;
      if (lint.size() > 1) {
          int index = getRnd50()%lint.size();
          value = lint.remove(index); 
      } else if (lint.size() == 1 ) {
          value = lint.remove(0);
      }      

      return value;      
  }

getRnd50()を正確に99回呼び出します。100個の整数のリストに格納されている数値は順番に並んでいるため、実際にはランダムではありません。

于 2013-01-02T15:09:26.043 に答える
0

コードのパフォーマンスの低下はその行にあります

if (getrnd50() <= 25)

生成された単一の乱数からより多くの情報を取得する方法を見つける必要があります。そうしないと、コストのかかる生成されたリソースが無駄になります。そのための私の提案は次のとおりです。

まず、0 から 15 までの乱数ジェネレーターがあるとします。すべての数値は、葉が数値を表すバイナリ ツリーのパスとして表すことができます。trueしたがって、ルートから開始するときに、ツリーを左に歩くたびにif 条件を評価すると言えます。

問題は、乱数ジェネレーターが 2 の累乗で終わらない間隔で数値を生成することです。そのため、そのツリーを拡張する必要があります。これは次のように行われます:
乱数が 0 から 31 の範囲にある場合、それらの数値のツリーで問題ありません。32 ~ 47 の範囲にある場合は 0 ~ 15 のツリーを使用し、48 ~ 49 の場合は 0 ~ 1 のツリーを使用します。

したがって、最悪の場合、その乱数からの情報をあまり使用していませんが、ほとんどの場合は使用しています。したがって、これにより平均的なケースが大幅に改善されるはずです。

于 2013-01-02T14:54:52.243 に答える