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()（或将它们中的两个相乘）怎么办？

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 的概率的四倍，那么如果是一个纸质练习，你可能会在一个充满的网格上：

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属于哪个bin。最简单的方法是使用最明显的循环：

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) 的线下方的框的总和。所以它是图形下方的区域，图形是一个简单的直角三角形。所以你可以从面积公式倒推。

具体来说，图下方从 (0, 0) 到 (n, n) 在位置 x 处的区域为 (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 回答