C++ 具有频繁变化概率的离散分布采样

问题：我需要从由某些权重构成的离散分布中进行采样，例如{w1,w2,w3,..}，因此概率分布为 {p1,p2,p3,...}，其中 pi=wi/(w1+w2+...)。

有些wi变化非常频繁，但只占所有wi的比例非常低。但分布本身每次发生时都必须重新规范化，因此我相信 Alias 方法不能有效地工作，因为每次都需要从头开始构建整个分布。

我目前想到的方法是二叉树（堆方法），其中所有wi都保存在最低层，然后在更高层保存每两个的和，依此类推。所有这些的总和将处于最高水平，这也是归一化常数。因此，为了在 wi 发生变化后更新树，需要进行 log(n) 次更改，以及相同数量的更改以从分布中获取样本。

问题：

Q1.您对如何更快地实现它有更好的想法吗？ Q2。最重要的部分：我正在寻找一个已经做到这一点的图书馆。

解释：几年前我自己通过在向量中构建堆结构来完成此操作，但从那时起我学到了很多东西，包括发现库（:)）和诸如地图之类的容器......现在我需要重写该代码具有更高的功能，这次我想做对：

所以 Q2.1 是否有一种很好的方法来使 C++ 映射不按索引排序和搜索，而是按其元素的累积和进行排序和搜索（这就是我们采样的方式，对吗？..）。 （这是我目前的理论，我想如何做到这一点，但不一定要这样......）

Q2.2 也许有一些更好的方法来做同样的事情？我相信这个问题如此频繁，以至于我很惊讶我找不到某种可以为我做这件事的图书馆......

非常感谢你，如果有人以其他形式问这个问题，我很抱歉，请指导我，但我花了很长时间寻找......

-z

编辑：我可能还需要删除或添加元素，但我think如果这会产生巨大的差异，我可以避免它，从而只需要改变权重的值。

Edit2：权重一般来说是实数，我必须考虑是否可以将它们设为整数......

我实际上会使用字符串的哈希集（不记得它的 C++ 容器，但您可能需要实现自己的容器）。为每个 i 放置 wi 元素，其值是“w1_1”、“w1_2”...一直到“w1_[w1]”（即以“w1_”开头的 w1 元素）。

当您需要采样时，使用均匀分布随机选择一个元素。如果您选择了 w5_*，则假设您选择了元素 5。由于哈希中的元素数量，这将为您提供所需的分布。

现在，当 wi 从 A 变为 B 时，只需将 B-A 元素添加到哈希中（如果 B>A），或者删除 wi 的最后一个 A-B 元素（如果 A>B）。

在这种情况下，添加新元素和删除旧元素是微不足道的。

显然，问题是“随机选择一个元素”。如果您的散列是封闭散列，则您随机选择一个数组单元格，如果它是空的 - 只需再次随机选择一个。如果你的哈希值比权重总和大 3 或 4 倍，那么你的复杂度将会相当不错：检索随机样本需要 O(1)，修改权重需要 O(|A-B|)。

另一种选择是，由于只有一小部分权重发生变化，因此将权重分为两部分 - 固定部分和更改部分。那么你只需要关心改变的部分的变化，以及改变的部分的总重量与不变的部分的总重量之间的差异。然后对于固定部分，你的散列变成一个简单的数字数组：1 出现 w1 次，2 出现 w2 次，等等......，选择一个随机固定元素只是选择一个随机数。