4

List<int>非常に遅いリモート乱数生成ソースからバイト（ちょうど）を読み取るものを書いています。それと私の個人的な要件のために、ソースからできるだけ少ないバイトを取得したいと思います。

今、私は署名が次のように見えるメソッドを実装しようとしています：

int getRandomInteger(int min, int max)

ランダムなソースからバイトをフェッチし、それらを整数に変換する方法には2つの理論があります。

アプローチ＃1はナイーブです。(max - min) / 256バイト数を取得して合計します。それは機能しますが、私が持っている遅い乱数ジェネレーターソースから多くのバイトをフェッチします。たとえば、100万から0までのランダムな整数を取得したい場合、4000バイト近くをフェッチします...これは受け入れられません。

アプローチ＃2は私には理想的に聞こえますが、アルゴリズムを思い付くことができません。こんなふうになります：

例として、最小：0、最大：1000を取り上げます。

  • ceil(rangeSize / 256)この場合はどれであるかを計算しceil(1000 / 256) = 4ます。次に、ソースから1バイトをフェッチします。
  • この1バイトを0〜255の範囲から0〜3の範囲（または1〜4）にスケーリングし、使用するグループを決定します。たとえば、バイトが250の場合、4番目のグループ（最後の250の数値、範囲内の750〜1000を表す）を選択します。
  • 次に、別のバイトをフェッチし、0〜255から0〜250にスケーリングして、グループ内の位置を決定します。したがって、この2番目のバイトがたとえば120の場合、最終的な整数は750 + 120 = 870です。

そのシナリオでは、合計2バイトをフェッチするだけで済みました。ただし、範囲が0〜1000000であるかのように、いくつかの「グループ」が必要であるため、はるかに複雑です。

このようなものを実装するにはどうすればよいですか？Java / C＃/JavaScriptコードまたは擬似コードで大丈夫です。

また、結果がエントロピー/ランダム性を失わないようにしたいと思います。ですから、整数のスケーリングが少し心配です。

4

4 に答える 4

2

残念ながら、アプローチ＃1は壊れています。たとえば、最小値が0で最大値が510の場合、2バイトを追加します。結果を0にする方法は1つだけです。つまり、両方のバイトがゼロです。この可能性は（1/256）^2です。ただし、100 = 100 + 0、99 + 1、98 + 2など、他の値を取得する方法はたくさんあります。したがって、100の可能性ははるかに大きくなります：101（1/256）^2。

あなたが望むことをするための多かれ少なかれ標準的な方法は次のとおりです：

Let R = max - min + 1   -- the number of possible random output values
Let N = 2^k >= mR, m>=1  -- a power of 2 at least as big as some multiple of R that you choose.
loop
   b = a random integer in 0..N-1 formed from k random bits
while b >= mR -- reject b values that would bias the output
return min + floor(b/m)

これは、拒否の方法と呼ばれます。出力にバイアスをかけるランダムに選択された2進数を破棄します。min-max+1たまたま2の累乗である場合、拒否はゼロになります 。

あなたが持っていてm=1、min-max+12の大きな力よりも1つ多い場合、拒否はほぼ半分になります。この場合、あなたは間違いなくもっと大きくしたいと思うでしょうm。

一般に、m値が大きいほど拒否は少なくなりますが、もちろん、数値ごとに必要なビット数はわずかに多くなります。選択する確率的に最適なアルゴリズムがありmます。

ここに示されている他の解決策のいくつかには問題がありますが、申し訳ありませんが、コメントする時間がありません。興味があれば多分数日で。

于 2012-11-10T16:59:09.513 に答える
1

3バイト（一緒に）は、0..16777215の範囲のランダムな整数を提供します。この値から20ビットを使用して、範囲0..1048575を取得し、1000000を超える値を破棄できます。

于 2012-11-10T16:39:18.907 に答える
1 
range 1 to r
256^a >= r

first find 'a' 

get 'a' number of bytes into array A[]

num=0
for i=0 to len(A)-1
    num+=(A[i]^(8*i))
next

random number = num mod range
于 2012-11-10T16:41:56.420 に答える
1

ランダム ソースは、呼び出しごとに 8 つのランダム ビットを提供します。[min,max] の範囲の整数の場合、ceil(log2(max-min+1)) ビットが必要になります。

何らかの関数を使用して、ソースからランダムなバイトを取得できると仮定します。

bool RandomBuf(BYTE* pBuf , size_t nLen); // fill buffer with nLen random bytes

次の関数を使用して、特定の範囲でランダムな値を生成できます。

// --------------------------------------------------------------------------
// produce a uniformly-distributed integral value in range [nMin, nMax]
// T is char/BYTE/short/WORD/int/UINT/LONGLONG/ULONGLONG
template <class T> T RandU(T nMin, T nMax)
{
    static_assert(std::numeric_limits<T>::is_integer, "RandU: integral type expected");

    if (nMin>nMax)
        std::swap(nMin, nMax);

    if (0 == (T)(nMax-nMin+1)) // all range of type T
    {
        T nR;
        return RandomBuf((BYTE*)&nR, sizeof(T)) ? *(T*)&nR : nMin;
    }

    ULONGLONG nRange    = (ULONGLONG)nMax-(ULONGLONG)nMin+1        ; // number of discrete values
    UINT      nRangeBits= (UINT)ceil(log((double)nRange) / log(2.)); // bits for storing nRange discrete values
    ULONGLONG nR                                                   ;

    do
    {
        if (!RandomBuf((BYTE*)&nR, sizeof(nR)))
            return nMin;

        nR= nR>>((sizeof(nR)<<3) - nRangeBits); // keep nRangeBits random bits
    }
    while (nR >= nRange);                       // ensure value in range [0..nRange-1]

    return nMin + (T)nR;                        // [nMin..nMax]
}

常に 8 ビットの倍数を取得しているため、呼び出し間で余分なビットを節約できます (たとえば、16 ビットのうち 9 ビットだけが必要な場合があります)。いくつかのビット操作が必要であり、努力する価値があるかどうかを判断するのはあなた次第です。

「半ビット」を使用すれば、さらに節約できます: [1..5] の範囲の数値を生成するとします。ランダム値ごとに log2(5)=2.32 ビットが必要です。32 個のランダム ビットを使用すると、実際にはこの範囲で floor(32/2.32)= 13 個のランダム値を生成できますが、追加の作業が必要になります。

于 2012-11-10T16:42:30.490 に答える