问题:我需要从由某些权重构成的离散分布中抽样，例如{w1，w2，w3，..}，因此是概率分布{p1，p2，p3，...}，其中pi = wi/(w1 + w2 + ...)。
Wi的某些变化非常频繁，但在所有Wi的变化中只占很小的比例。但是，分发本身因此每次发生时都必须重新规范化，因此，我认为Alias方法不能有效地工作，因为每次都需要从头开始构建整个分发。
我目前正在考虑的方法是二叉树(堆方法)，其中所有wi都保存在最低级别中，然后将两个wis的总和保存在更高级别中，依此类推。它们的总和将处于最高水平，这也是一个归一化常数。因此，为了在wi更改后更新树，需要进行log(n)更改，以及从分布中获取样本的相同数量。
问题:
Q1。您对如何更快地实现它有更好的想法吗？
Q2。最重要的部分:我正在寻找一个已经做到这一点的图书馆。
说明:几年前，我已经通过在 vector 中构建堆结构来完成此操作，但是从那时起，我学到了很多东西，包括发现库(:)以及 map 之类的容器...现在，我需要重写该代码具有更高的功能，这次我想做对了:
所以Q2.1是一种使c++映射排序和搜索的好方法，它不是按索引而是按元素的累加总和来搜索(这是我们采样的方式，对吧？)。 (这是我目前的理论，我想怎么做，但不一定非要这样...)
Q2.2也许有一些更好的方法可以做到这一点？我相信这个问题如此频繁，以至于我找不到能够为我做的某种图书馆，这让我感到非常惊讶。
非常感谢，如果以其他形式询问过此内容，我感到非常抱歉，请直接向我指出，但是我在寻找时花了很多时间...
-z
编辑:有可能我可能也需要删除或添加元素，但是我认为我可以避免，如果那有很大的不同，那么只改变权重的值即可。
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次，依此类推，等等。选择一个随机的固定元素就是选择一个随机数。
关于具有频繁变化的概率的c++离散分布采样，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/25189406/