java - Java中的加权随机性

Question

在 Java 中，给定 n 个项目，每个项目的权重 w，如何从集合中随机选择一个具有等于 w 机会的项目em>？

假设每个权重是从 0.0 到 1.0 的 double ，并且集合中的权重总和为 1。Item.getWeight() 返回项目的权重。

Answer 1

2020 年更新(有趣的是，这在下面的 2011 版本中获得了 37 次投票，但有一个明显的错误):

• 修复了当 Math.random() 产生一个非常接近 1.0 的数字时无法选择最后一项的问题，并且我们在浮点精度方面不走运:随机索引结果是-1，这显然是错误的。
• 一些代码压缩
• 使用较少的变量名

Item[] items = ...;

// Compute the total weight of all items together.
// This can be skipped of course if sum is already 1.
double totalWeight = 0.0;
for (Item i : items) {
    totalWeight += i.getWeight();
}

// Now choose a random item.
int idx = 0;
for (double r = Math.random() * totalWeight; idx < items.length - 1; ++idx) {
    r -= items[idx].getWeight();
    if (r <= 0.0) break;
}
Item myRandomItem = items[idx];

---

2011版(留作比较):

Item[] items = ...;

// Compute the total weight of all items together
double totalWeight = 0.0d;
for (Item i : items)
{
    totalWeight += i.getWeight();
}
// Now choose a random item
int randomIndex = -1;
double random = Math.random() * totalWeight;
for (int i = 0; i < items.length; ++i)
{
    random -= items[i].getWeight();
    if (random <= 0.0d)
    {
        randomIndex = i;
        break;
    }
}
Item myRandomItem = items[randomIndex];

---