java - 如何有效地生成一组具有预定义分布的唯一随机数？

Question

我有一个具有某种概率分布的项目图:

Map<SingleObjectiveItem, Double> itemsDistribution;

给定一个特定的m我必须生成一个 Set的 m从上述分布中采样的元素。

截至目前，我使用的是天真的方式:

while(mySet.size < m)
   mySet.add(getNextSample(itemsDistribution));

getNextSample(...)方法根据其概率从分布中获取对象。现在，作为 m增加性能严重受损。对于 m = 500和 itemsDistribution.size() = 1000元素，抖动太多，函数在 while 循环中停留的时间太长。生成 1000 个这样的集合，你就有了一个可以爬行的应用程序。

是否有更有效的方法来生成一组具有“预定义”分布的唯一随机数？大多数集合改组技术等都是一致随机的。解决这个问题的好方法是什么？

更新:循环将调用 getNextSample(...) “至少”1 + 2 + 3 + ... + m = m(m+1)/2次。那是在第一次运行中我们肯定会得到一个样本。第二次迭代，它可能至少被调用两次，依此类推。如果getNextSample本质上是顺序的，即遍历整个累积分布来找到样本，那么循环的运行时复杂度至少为:n*m(m+1)/2 , 'n' 是分布中元素的数量。如果m = cn; 0<c<=1那么循环至少是 Sigma(n^3)。这也是下限!

如果我们用二进制搜索代替顺序搜索，复杂度至少为 Sigma(log n * n^2)。高效但可能不会大幅提升。

此外，由于我将上述循环称为 k，因此无法从分发中删除次，生成 k这样的集合。这些套装是元素随机“时间表”的一部分。因此是一组“项目”。

Answer 1

首先在二维中生成一些随机点。

然后应用你的分布

现在找到分布中的所有条目并选择 x 坐标，您将获得具有请求分布的随机数，如下所示: