-2

を満たす均一な整数を生成したい0 <= result <= maxValue。

組み込みの符号なし整数型の全範囲で均一な値を返すジェネレーターがすでにあります。byte Byte()this 、、、およびushort UInt16()のメソッドを呼び出しましょう。これらの方法の結果は完全に均一であると仮定します。uint UInt32()ulong UInt64()

uint UniformUInt(uint maxValue)私が欲しいメソッドのシグネチャはとですulong UniformUInt(ulong maxValue)。

私が探しているもの：

  1. 正し
    さ私は、戻り値が指定された間隔で分散されることを望みます。
    ただし、パフォーマンスが大幅に向上する場合は、非常に小さなバイアスでもかまいません。つまり、2^64の値が与えられた場合に2/3の確率で識別を可能にする次数のバイアスを意味します。
    どのに対しても正しく機能する必要がありますmaxValue。
  2. パフォーマンス
    メソッドは高速である必要があります。
  3. 効率
    この方法では、基になるジェネレーターによっては生のバイトの生成にコストがかかる可能性があるため、生のランダム性はほとんど消費されません。数ビットを無駄にすることは問題ありませんが、単一の数値を生成するためにたとえば128ビットを消費することはおそらく過剰です。

一部のメンバー変数で、前の呼び出しから残ったランダム性をキャッシュすることもできます。

intオーバーフローとラッピング動作に注意してください。

私はすでに解決策を持っています（答えとして投稿します）が、私の好みには少し醜いです。だから私はより良い解決策のアイデアを得たいと思います。

maxValue2^64個のバケットと2^74個のランダムな値でヒストグラムを生成できないため、大きなsで単体テストを行う方法についての提案も役立ちます。もう1つの厄介な問題は、特定のバグでは、一部のmaxValueディストリビューションのみが大きくバイアスされ、他のディストリビューションはごくわずかしかバイアスされないことです。

4

3 に答える 3

2

汎用的なソリューションとして、このようなものはどうでしょうか。このアルゴリズムは、 Java のnextIntメソッドで使用されるアルゴリズムに基づいており、不均一な分布を引き起こす値を拒否します。UInt32メソッドの出力が完全に均一である限り、これも均一である必要があります。

uint UniformUInt(uint inclusiveMaxValue)
{
    unchecked
    {
        uint exclusiveMaxValue = inclusiveMaxValue + 1;

        // if exclusiveMaxValue is a power of two then we can just use a mask
        // also handles the edge case where inclusiveMaxValue is uint.MaxValue
        if ((exclusiveMaxValue & (~exclusiveMaxValue + 1)) == exclusiveMaxValue)
            return UInt32() & inclusiveMaxValue;

        uint bits, val;
        do
        {
            bits = UInt32();
            val = bits % exclusiveMaxValue;

            // if (bits - val + inclusiveMaxValue) overflows then val has been
            // taken from an incomplete chunk at the end of the range of bits
            // in that case we reject it and loop again
        } while (bits - val + inclusiveMaxValue < inclusiveMaxValue);

        return val;
    }
}

拒否プロセスは、理論的には永久にループし続ける可能性があります。実際には、パフォーマンスはかなり良いはずです。(a)予想される使用パターン、および(b)基礎となる RNG のパフォーマンス特性を知らずに、一般的に適用可能な最適化を提案することは困難です。

たとえば、ほとんどの呼び出し元が最大値 <= 255 を指定する場合、毎回 4 バイトの乱数を要求するのは意味がないかもしれません。一方、より少ないバイト数を要求することによるパフォーマンス上の利点は、実際に必要なバイト数を常にチェックする追加のコストよりも優先される場合があります。(そしてもちろん、特定の情報が得られたら、結果が十分に良くなるまで最適化とテストを続けることができます。)

于 2012-03-01T00:39:08.680 に答える
1

彼が答えであるかどうかはわかりません。コメントよりもスペースが必要なのは間違いないので、ここに書く必要がありますが、他の人がこれがばかげていると思う場合は、喜んで削除します.

私が得たOQから、それは

  1. エントロピービットは非常に高価です
  2. 他のすべては高価であると考えるべきですが、エントロピーほどではありません。

私の考えは、2 進数を 2 分の 1、4 分の 1 に使用することです。のようなもの

例として maxValue=333 (10 進数) を使用し、getBit()ランダムに 0 または 1 を返す関数を想定します。

offset:=0
space:=maxValue

while (space>0)

  //Right-shift the value, keeping the rightmost bit this should be 
  //efficient on x86 and x64, if coded in real code, not pseudocode
  remains:=space & 1
  part:=floor(space/2)
  space:=part

  //In the 333 example, part is now 166, but 2*166=332 If we were to simply chose one
  //half of the space, we would be heavily biased towards the upper half, so in case
  //we have a remains, we consume a bit of entropy to decide which half is bigger

  if (remains)
    if(getBit())
      part++;

  //Now we decide which half to chose, consuming a bit of entropy
  if (getBit())
    offset+=part;

  //Exit condition: The remeinind number space=0 is guaranteed to be met
  //In the 333 example, offset will be 0, 166 or 167, remaining space will be 166
}

randomResult:=offset

getBit()ビットベースの場合はエントロピーソースから取得するか、最初の呼び出しで n ビットのエントロピーを一度に消費し (エントロピーソースに最適なのは明らかに n です)、これを空になるまでシフトします。

于 2012-02-29T13:30:59.660 に答える
0

私の現在の解決策。私の好みには少し醜い。また、生成された数値ごとに 2 つの分割があるため、パフォーマンスに悪影響を与える可能性があります (この部分はまだプロファイルしていません)。

uint UniformUInt(uint maxResult)
{
    uint rand;
    uint count = maxResult + 1;

    if (maxResult < 0x100)
    {
        uint usefulCount = (0x100 / count) * count;
        do
        {
            rand = Byte();
        } while (rand >= usefulCount);
        return rand % count;
    }
    else if (maxResult < 0x10000)
    {
        uint usefulCount = (0x10000 / count) * count;
        do
        {
            rand = UInt16();
        } while (rand >= usefulCount);
        return rand % count;
    }
    else if (maxResult != uint.MaxValue)
    {
        uint usefulCount = (uint.MaxValue / count) * count;//reduces upper bound by 1, to avoid long division
        do
        {
            rand = UInt32();
        } while (rand >= usefulCount);
        return rand % count;
    }
    else
    {
        return UInt32();
    }
}

ulong UniformUInt(ulong maxResult)
{
    if (maxResult < 0x100000000)
        return InternalUniformUInt((uint)maxResult);
    else if (maxResult < ulong.MaxValue)
    {
        ulong rand;
        ulong count = maxResult + 1;
        ulong usefulCount = (ulong.MaxValue / count) * count;//reduces upper bound by 1, since ulong can't represent any more
        do
        {
            rand = UInt64();
        } while (rand >= usefulCount);
        return rand % count;
    }
    else
        return UInt64();
}
于 2012-02-29T12:40:05.430 に答える