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

一尘不染

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

algorithm

我有一些概率分布的项目图：

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此类集合，因此无法从分布中删除。这些集合是项目的随机“计划”的一部分。因此是一套“物品”。

阅读 204

2020-07-28

共1个答案

一尘不染

问题不太可能是您显示的循环：

令n为分布的大小，我为getNextSample的调用次数。我们有I =
sum_i（C_i），其中C_i是集合大小为i时getNextSample的调用次数。为了找到E
[C_i]，请注意C_i是泊松过程的到达时间，其中λ=
1-i / n，因此与λ
呈指数分布。因此，E [C_i] = 1
/λ=因此E [C_i] = 1 /（1-i / n）<= 1 /（1-m / n）。因此，E [I] <m /（1-m / n）。

也就是说，对一组大小为m = n / 2的样本进行采样平均将少于getNextSample的2m =
n调用。如果那是“缓慢的”和“爬行”，则可能是因为getNextSample缓慢。考虑到将分布传递给方法的不合适方式，这实际上不足为奇（因为该方法将必须遍历整个分布以找到随机元素）。

以下内容应更快（如果m <0.8 n）

class Distribution<T> {
    private double[] cummulativeWeight;
    private T[] item;
    private double totalWeight;

    Distribution(Map<T, Double> probabilityMap) {
        int i = 0;

        cummulativeWeight = new double[probabilityMap.size()];
        item = (T[]) new Object[probabilityMap.size()];

        for (Map.Entry<T, Double> entry : probabilityMap.entrySet()) {
            item[i] = entry.getKey();
            totalWeight += entry.getValue();
            cummulativeWeight[i] = totalWeight;
            i++;
        }
    }

    T randomItem() {
        double weight = Math.random() * totalWeight;
        int index = Arrays.binarySearch(cummulativeWeight, weight);
        if (index < 0) {
            index = -index - 1;
        }
        return item[index];
    }

    Set<T> randomSubset(int size) {
        Set<T> set = new HashSet<>();
        while(set.size() < size) {
            set.add(randomItem());
        }
        return set;
    }
}



public class Test {

    public static void main(String[] args) {
        int max = 1_000_000;
        HashMap<Integer, Double> probabilities = new HashMap<>();
        for (int i = 0; i < max; i++) {
            probabilities.put(i, (double) i);
        }

        Distribution<Integer> d = new Distribution<>(probabilities);
        Set<Integer> set = d.randomSubset(max / 2);
        //System.out.println(set);
    }
}

预期的运行时间为O（m /（1-m / n）* log n）。在我的计算机上，在大约3秒钟内计算出一组1_000_000的大小为500_000的子集。

如我们所见，当m接近n时，预期的运行时间接近无穷大。如果这是一个问题（即，m> 0.9 n），则以下更复杂的方法应该会更好地工作：

Set<T> randomSubset(int size) {
    Set<T> set = new HashSet<>();
    while(set.size() < size) {
        T randomItem = randomItem();
            remove(randomItem); // removes the item from the distribution
            set.add(randomItem);
    }
    return set;
}

为了有效地实现删除，需要使用不同的分布表示形式，例如，一个二叉树，其中每个节点存储其根为根的子树的总权重。

但这很复杂，因此如果已知m明显小于n，我就不会走那条路线。

2020-07-28