1

我正在使用 C++ 中大约 2000 个元素的数组。

每个元素代表该元素被随机选择的概率。

然后，我将此数组转换为累积数组，目的是使用它来计算掷骰子时选择哪个元素。

示例数组：{1,2,3,4,5}

示例累积数组：{1,3,6,10,15}

当滚动数字 3、4 或 5 时，我希望能够在累积数组中选择 3。

增加的复杂性是我的数组由长双精度数组成。这是几个连续元素的示例：

0.96930161525189592646367317541056252139242133125662803649902343750 0.96941377254127855667142910078837303444743156433105468750000000000 0.96944321382974149711383993199831365927821025252342224121093750000 0.96946143938926617454089618153290075497352518141269683837890625000 0.96950069444055009509463721739663810694764833897352218627929687500 0.96951751803395748961766908990966840065084397792816162109375000000

这可能是用这个数据集做加权概率的一种糟糕的方法，所以我愿意接受任何关于解决这个问题的更好方法的建议。

4

4 回答 4

2

您可以使用partial_sum：

unsigned int SIZE = 5;
int array[SIZE] = {1,2,3,4,5};
int partials[SIZE] = {0};

partial_sum(array, array+SIZE, partials);
// partials is now {1,3,6,10,15}

您想要从数组中获得的值可从部分总和中获得：

12 == array[2] + array[3] + array[4];

12 == partials[4] - partials[1];

总计显然是部分和中的最后一个值：

15 == partial[4];
于 2013-02-19T10:02:43.730 回答
1

您实际上可以使用流选择来执行此操作，而无需计算部分和数组。这是我在 Java 中的代码：

public static int selectRandomWeighted(double[] wts, Random rnd) {
    int selected = 0;
    double total = wts[0];

    for( int i = 1; i < wts.length; i++ ) {
        total += wts[i];

        if( rnd.nextDouble() <= (wts[i] / total)) {
            selected = i;
        }
    }

    return selected;        
}

如果您想在总和中保留尽可能多的精度位数，则可以使用Kahan 求和进一步改进上述内容。

但是，如果你想重复从这个数组中提取，那么预先计算一个部分和的数组并使用二进制搜索来找到正确的索引会更快。

于 2013-02-21T04:45:33.817 回答
1

考虑将信息存储为整数分子和分母，以便在最后一步之前不会损失精度。

于 2013-02-18T17:29:02.813 回答
0

好的，我想我已经解决了这个问题。

我只是做了一个二分搜索，而不是仅仅拥有

if (arr[middle] == value)

我在 OR 中添加了

if (arr[middle] == value || (arr[middle] < value && arr[middle+1] > value))

这似乎以我希望的方式处理它。

于 2013-02-18T17:09:24.480 回答