选择一个随机加权元素，带样本，无替换

Question

给定一个表示战利品奖励的结构 table，其中 a 是奖励类型，2 是整数权重，这意味着 a 被拉出的可能性是 d 的两倍。

Map{
  "a" -> 2
  "b" -> 2
  "c" -> 2
  "d" -> 1
  "e" -> 1
  "f" -> 1
}

如何生成用于展示目的的示例 + 获胜者？

我当前的（伪）代码：

list out;
foreach(entry:map){
  for(entry.value){
    out.add(a)
  }
}

然后创建一个示例进行展示。

Collections.shuffle(out);
List display = out.stream()
  .distinct()
  .limit(8)
  .collect(Collectors.toList());

使用此代码，如果我通过

选择获胜者，我能否相信 .distinct 不会影响赔率

winner = display.get(0);

我意识到添加最后一个元素可能会扭曲结果，因为在 distinct 调用发生后，它会更多更有可能选择一个权重较低的数字.

但是选择流的第一个元素应该是值得信赖的，对吧？因为它是在 .distinct 具有状态诱导效果之前选择的？

Answer 1

您的数据结构实现似乎有点奇怪。我会做这样的事情：

Map{
  0 -> "a"
  2 -> "b"
  4 -> "c"
  5 -> "d"
  6 -> "e"
  7 -> "f"
}

然后，为了让事情变得更快（或者允许非常大的战利品 table），我会得到一个像 int maxValue = 7 这样的值。现在，要从 table 中获取战利品，我只需调用 0 和 maxValue（含）之间的随机整数 lootDrop。然后我可以遍历我的 table 以找到小于或等于 lootdrop 的最大值。如果您需要将映射保留为 string to integer 映射，并控制整数映射，那么这样做也很简单。

如果你不想走那么远，你可以简单地在你的解决方案中得到一个介于 0 和 8 之间的随机整数，它仍然有效。

你坚持这个公式有什么理由吗？

Answer 2

看看Stochastic universal sampling and Fitness proportionate selection。根据权重取一个样本的简单方法可以通过将每个元素表示为长度与其权重成比例的区间来解释。例如：

Map{
  "a" -> 2 // weight 2
  "b" -> 2
  "c" -> 2
  "d" -> 1
  "e" -> 1
  "f" -> 1
}
=>
Map{
  "a" -> (0,2) // weight 2 -- is now length of the interval
  "b" -> (2,4) // ...
  "c" -> (4,6)
  "d" -> (6,7)
  "e" -> (7,8)
  "f" -> (8,9)
}

然后您从 0 到 9 9*Math.random() 中选择随机数（作为指向范围的指针）并检查它属于哪个区间——这是您的随机样本 w.r.t 输入权重。重复直到获得所需数量的样本（如果需要，可以忽略重复项）...

当然这是一个有点惯用的解释，在实际代码中你会只保留上限，因为下限只是前一个元素的上限。然后你会选择第一个在 随机指针 .

上方有边界的元素

更新：从数学的角度来看，你原来的重复元素的方法是可以的（选择具有双倍权重的元素的概率是双倍的），但是当权重很高时这将是一个问题：Map{"a"->1000 "b"->100000}.它也不能很好地处理实值权重。

Answer 3

我喜欢 Martin 的回答，但根据他提出的性能问题，我也会 post 作为 caveat/alternative 我自己的回答。可以使用 Map 实现与他自己的非常相似的实现（我将使用 HashMap，因为它是我的最爱）。

private final AtomicLong idxCounter = new AtomicLong(0);
private final Map<Long, Item> dropTable = new HashMap<>();
public void addDrop(Item item, long relativeFrequency) {
    while (relativeFrequency-- > 0) {
        Long nextIdx = idxCounter.getAndIncrement();
        dropTable.put(nextIdx, item);
    }
}

private static final Random rng = new Random(System.currentTimeMillis());
public Item getRandomDrop() {
    Long size = idxCounter.get();
    // randomValue will be something in the interval [0, size), which 
    // should cover the whole dropTable.
    // See  for a fair
    // implementation of nextLong.
    Long randomValue = nextLong(rng, size); 
    return dropTable.get(randomValue); 
}

从 HashMap 中通过键获取值非常快。您可以通过指定 dropTable 初始容量和负载因子（参见 javadoc for HashMap）进一步优化它，但这取决于您自己的判断。

它也是线程安全的，只要没有其他东西在玩弄 dropTable!

选择一个随机加权元素，带样本，无替换

Pick a random weighted element, with sample, no replacement

java

random

probability