java - 加权随机数 : boundary case

Question

引用此 post 中给出的最佳答案，我注意到当 rnd=sum_of_weight 时，它在边界情况下失败。解决方法是在 [0,sum_of_weight) 中生成随机数，但是我想知道为什么代码对于这种边界情况会失败？是不是算法有问题？

编辑:此外，权重数组是否需要从高到低排序？看起来是这样，基于减法循环。

下面是实现上述帖子中伪代码的Java代码。

int sum_of_weight = 0;



int []choice_weight = {50, 15, 15, 10, 10};         // percentages
int num_choices = choice_weight.length;

public void init() {

    for (int i = 0; i < num_choices; i++) {
        sum_of_weight += choice_weight[i];
    }
}

int next() {
    int rnd = (int)Util.between(0, sum_of_weight);// random(sum_of_weight);
    rnd=sum_of_weight;                      // force the exception by hitting boundary case
    //System.out.print("rnd=" + rnd);
    for (int i = 0; i < num_choices; i++) {
        if (rnd < choice_weight[i])
            return i;
        rnd -= choice_weight[i];
    }

    throw new RuntimeException("should never get here for rnd=" + rnd);
}

public static void main(String[] args) {
    SimpleWeight sw = new SimpleWeight();
    sw.init();
    for (int i=0; i < 10;i++) {
        System.out.println(sw.next());
    }
}

Answer 1

算法的第 2 步 you link to状态:

2) pick a random number between 0 and less than the sum weights.

对我来说，这清楚而明确地表明正确的方法是从 [0,sum_of_weight) 中选择一个数字。从不同的范围(例如任何包含 sum_of_weight 的范围)中选择一个数字不是算法的缺陷，而是该算法实现的缺陷。 p>

edit 不，不需要为算法工作对权重进行排序。