1

我有 3 个 IP,每个 IP 都有一个权重,我想使用随机函数根据其权重返回 IP,例如,如果我们有 3 个 IP:X 权重为 6,Y 权重为 4,Z 权重2,我想在 50% 的情况下返回 X,在 33% 的情况下返回 Y,在 17% 的情况下返回 Z,这取决于 C 中的随机函数。

此代码适用于 3 个 IP 的情况:

double r = rand() / (double)RAND_MAX;
double denom = 6 + 4 + 2;
if (r < 6 / denom) {
// choose X
} else if (r < (6 + 4) / denom) {
// choose Y 
} else {
// choose Z
}

如果我有 n 个 IP,如何修改代码以处理 n 个 IP 而不是特定数量的 IP?

4

2 回答 2

1

这是如何执行此操作的示例

加权随机数

从那个帖子:

int sum_of_weight = 0;
for(int i=0; i<num_choices; i++) {
   sum_of_weight += choice_weight[i];
}
int rnd = random(sum_of_weight);
for(int i=0; i<num_choices; i++) {
  if(rnd < choice_weight[i])
    return i;
  rnd -= choice_weight[i];
}
assert(!"should never get here");
于 2013-08-27T16:30:34.177 回答
0

用ip的累积权重构建一个数组

像这样的东西

// C99 code
int pick_ip(int weights[], int nweights)
{
    // note you can split this step out if you like (a good plan)
    int cum_weights[nweights];
    int tot_weight = 0;
    for(int i=0; i < nweights; i++)
    {
        tot_weight += weights[i];
        cum_weights[i] = tot_weight;
    }

    int t = (int)(tot_weight * rand() / (double)RAND_MAX);

    if(cum_weights[0] > t) { return 0; }

    // binary search for point that we picked
    int v = -1;
    int l = 0, u = nweights -1;
    int m = u/2;
    do { // binary search
        if(cum_weights[m] > t) u = m;
        else l = m;
        m = (u + l)/2;
        if(cum_weights[l+1] >  t) {v=l+1; break;}
        if(cum_weights[u-1] <= t) {v=u;   break;}
    } while(1);
}

注意:如果您要进行大量挑选,请拆分累积分布数组的构建。此外,如果您想要浮点权重,则需要使用 Khan 总和来计算累积权重(如果您想要代码来执行该注释,我可以将其添加到我的示例中)

于 2013-08-27T16:29:18.303 回答