在布尔数组(分位数函数)上具有低百分比的Java随机

Question

我有一个大约有10000个元素的布尔数组。我想用相当低的集合概率（cca 0,1-0,01）更改元素的值，同时知道更改元素的索引。脑海中浮现的代码类似于：

int count = 10000;
Random r = new Random();
for (int i = 0; i < count; i++) {
    double x = r.nextDouble();
    if (x < rate) {
            field[i]=!field[i];
            do something with the index...
    }
}

然而，当我在一个更大的循环中（不可避免地）这样做时，这是缓慢的。我唯一能想到的另一种可能性是使用分位数函数（高斯数学），但我还没有找到任何可以免费使用的代码或库。你知道如何解决这个问题吗？或者可以使用任何库（最好是标准库）吗？

Answer 1

基本上，您已经建立了一个具有n == count和p == rate的二项式模型。您应该得到的相关数值x可以建模为具有中心n*p == count*rate和标准偏差sigma == Math.sqrt(p*(1-p)/n) == Math.sqrt(rate * (1-rate) / count)的正态模型。

你可以很容易地计算

int x = (int) Math.round(Math.sqrt(rate * (1-rate) / count)
        * r.nextGaussian() + count * rate)

然后，您可以使用以下代码生成该范围内的x随机数。

Set<Integer> indices = new HashSet<Integer>();
while(indices.size() < x){
     indices.add(r.nextInt(count));
}

indices现在将包含正确的索引，您可以根据需要使用这些索引。

您只需要比x多一点地调用nextInt，这应该比您以前调用count的次数要少得多。