4

の範囲で一様に分布していない乱数を計算したいと思います[0, n - 1]。したがって、可能な最小値はゼロです。可能な最大値は n-1 です。最小値が最も頻繁に発生し、最大値が比較的まれに発生し、その間にほぼ線形の曲線があることを望みます(ガウスも問題ありません)。Objective-Cでこれを行うにはどうすればよいですか? (おそらく C ベースの API を使用)

私の現在のアイデアの大まかなスケッチは次のとおりです。

// min value w/ p = 0.7
// some intermediate value w/ p = 0.2
// max value w/ p = 0.1
NSUInteger r = arc4random_uniform(10);
if (r <= 6) 
    result = 0;
else if (r <= 8)
    result = (n - 1) / 2;
else
    result = n - 1;
4

2 に答える 2

1

arc4random_uniform()の戻り値を 2 乗(またはそれらの 2 つを乗算)しようとするとどうなるでしょうか。

int rand_nonuniform(int max)
{
    int r = arc4random_uniform(max) * arc4random_uniform(max + 1);
    return r / max;
}

私はそれをテストするためのサンプルプログラムをすぐに書きましたが、それは有望に見えます:

int main(int argc, char *argv[])
{
    int arr[10] = { 0 };

    int i;
    for (i = 0; i < 10000; i++) {
        arr[rand_nonuniform(10)]++;
    }

    for (i = 0; i < 10; i++) {
        printf("%2d. = %2d\n", i, arr[i]);
    }

    return 0;
}

結果：

0. = 3656
1. = 1925
2. = 1273
3. = 909
4. = 728
5. = 574
6. = 359
7. = 276
8. = 187
9. = 113
于 2013-02-06T20:56:03.363 に答える
1

あなたは基本的に正しい軌道に乗っていると思います。精度または範囲の問題が発生する可能性がありますが、一般に、たとえば 3、2、1、または 0 をランダムに選択する場合、3 を選択する確率を 0 を選択する確率の 4 倍にしたい場合、次のもので満たされたグリッドのすぐ下にある紙の演習：

3 3 3 3
2 2 2
1 1
0

何かを投げて、着地した数字を読みます。

目的の線形スケールのオプションの数は次のとおりです。

- 1 if number of options, n, = 1
- 1 + 2 if n = 2
- 1 + 2 + 3 if n = 3
- ... etc ...

これは、等差数列の単純な合計です。n(n+1)/2 の可能な結果が得られます。たとえば、n = 1 の場合は 1 * 2 / 2 = 1 です。n = 2 の場合は 2 * 3 /2 = 3 です。n = 3 の場合は 3 * 4 / 2 = 6 です。

したがって、すぐに次のように記述します。

NSUInteger random_linear(NSUInteger range)
{
    NSUInteger numberOfOptions = (range * (range + 1)) / 2;
    NSUInteger uniformRandom = arc4random_uniform(numberOfOptions);

    ... something ...
}

その時点で、uniformRandom がどのビンに分類されるかを決定する必要があります。最も簡単な方法は、最も明白なループを使用することです。

NSUInteger random_linear(NSUInteger range)
{
    NSUInteger numberOfOptions = (range * (range + 1)) / 2;
    NSUInteger uniformRandom = arc4random_uniform(numberOfOptions);

    NSUInteger index = 0;
    NSUInteger optionsToDate = 0;
    while(1)
    {
        if(optionsToDate >= uniformRandom) return index;
        index++;
        optionsToDate += index;
    }
}

反復せずに optionsToDate を計算できることを考えると、すぐに明らかなより高速な解決策は二分探索です。

さらに賢い見方をすると、uniformRandom は (0, 0) から (n, n) までの線の下にあるボックスの合計です。グラフの下の領域で、グラフは単純な直角三角形です。したがって、面積式から逆算できます。

具体的には、位置 x の (0, 0) から (n, n) までのグラフの下の領域は (x*x)/2 です。つまり、x を探しています。

(x-1)*(x-1)/2 <= uniformRandom < x*x/2

=> (x-1)*(x-1) <= uniformRandom*2 < x*x
=> x-1 <= sqrt(uniformRandom*2) < x

その場合、結果が数値グリッドの次の離散列に進まなかったため、x-1 を取得する必要があります。したがって、平方根演算の単純な整数の切り捨てでそこに到達できます。

したがって、途中で正確な不等式を混乱させていないと仮定し、すべての精度が適合すると仮定します。

NSUInteger random_linear(NSUInteger range)
{
    NSUInteger numberOfOptions = (range * (range + 1)) / 2;
    NSUInteger uniformRandom = arc4random_uniform(numberOfOptions);

    return (NSUInteger)sqrtf((float)uniformRandom * 2.0f);
}
于 2013-02-06T20:57:12.610 に答える