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

Question

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

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

我目前正在考虑的方法是二叉树(堆方法),其中所有wi都保存在最低级别,然后是两个级别在更高级别中的总和,依此类推.所有这些的总和将处于最高级别,这也是归一化常数.因此,为了在wi中更改后更新树,需要进行log(n)更改,以及从分发中获取样本的相同数量.

题:

Q1.你对如何更快地实现它有更好的想法吗？Q2.最重要的部分:我正在寻找一个已经完成这项工作的图书馆.

解释:几年前我自己做了这个,通过在向量中构建堆结构,但从那时起我学到了很多东西,包括发现库(:))和容器如map ...现在我需要重写代码具有更高的功能,我想这次正确:

所以Q2.1有一个很好的方法可以使c ++地图不是通过索引进行排序和搜索,而是通过它的元素的累积总和(这是我们如何采样,对吧？).(这是我目前的理论,我想怎么做,但它不一定要这样......)

Q2.2也许还有一些更好的方法可以做到这一点？我会相信这个问题是如此频繁,我很惊讶我找不到某种能为我做这件事的图书馆......

非常感谢,如果有其他形式的问题,我很抱歉,请指导我,但我花了很长时间看...

-z

编辑:我可能需要删除或添加元素,但我认为我可以避免它,如果这会产生巨大的差异,因此只留下改变权重的值.

Edit2:权重一般是实数,我不得不考虑是否可以使它们成为整数...

Answer 1

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

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

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

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

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

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