Java 中的加权随机性 [英] Weighted randomness in Java

问题描述

在Java中，给定n个物品，每个物品的权重为w，如何从集合中随机选择一个物品的概率等于wem>?

In Java, given n Items, each with weight w, how does one choose a random Item from the collection with a chance equal to w?

假设每个权重是从 0.0 到 1.0 的双精度值，并且集合中的权重总和为 1.Item.getWeight() 返回 Item 的权重.

Assume each weight is a double from 0.0 to 1.0, and that the weights in the collection sum to 1. Item.getWeight() returns the Item's weight.

推荐答案

2020 更新(有趣的是，这在 2011 年版本中获得了 37 个赞成票，并存在明显的错误):

2020 Update (interesting how this got 37 upvotes with a glaring bug in the 2011 version below):

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

• Fix the impossibility to select the last item when Math.random() yields a number very close to 1.0, and we are unlucky with floating point precision: random index -1 would be the result, which is obviously wrong.
• Some code compaction
• Less variable names used

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 版本(留作对比):

---

2011 version (for comparison left in):

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];

这篇关于Java 中的加权随机性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！