0

I have a boolean array of aproximattely 10 000 elements. I would like to with rather low,set probability (cca 0,1-0,01) change the value of the elements, while knowing the indexes of changed elements. The code that comes to mind is something like:

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...
    }
}

However, as I do this in a greater loop (inevitably), this is slow. The only other possibility that I can come up with is using quantile function (gaussian math), however I have yet to find any free to use code or library to use. Do you have any good idea how to work around this problem, or any library (standard would be best) that could be used?

5
  • could you provide a bit more code? what's fixed and genotype?
    – S. Pauk
    Mar 25, 2015 at 18:52
  • Sorry, that was mistake. Corrected
    – Rasty
    Mar 25, 2015 at 18:54
  • You could simply create (0.1 * 10000) random integers, with values between 0 and 9999: These would then exactly be the indices that you're looking for (and toggling the booleans based on these indices would be trivial and efficient).
    – Marco13
    Mar 25, 2015 at 19:05
  • I don`t know whether the integers would be any faster than generating the doubles. Well if yes that it might be nice to use them instead, however I would much prefer to just get a random number representing number of booleans to change corresponding to the given percantage, so that if the percantage was 50% (illustrative as it would be rather 0.005% than 50%) I would get 5000 most often. Or some similar algorithm or function.
    – Rasty
    Mar 25, 2015 at 19:14
  • Marco: Yeah, the problem is, that this is not how the probability works, there is some chance that not one will be changed, as well as is there a chance all will (ok, even ignoring these extreme and not exactly desirable cases, there should be some wariation in numbers)
    – Rasty
    Mar 25, 2015 at 23:36

1 Answer 1

1

Basically, you have set up a binomial model, with n == count and p == rate. The relevant number of values you should get, x, can be modeled as a normal model with center n*p == count*rate and standard deviation sigma == Math.sqrt(p*(1-p)/n) == Math.sqrt(rate * (1-rate) / count).

You can easily calculate

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

Then you can generate x random numbers in the range using the following code.

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

indices will now contain the correct indices, which you can use as you wish.

You'll only have to call nextInt a little more than x times, which should be much less than the count times you had to call it before.

1
  • Thanks a lot. I was looking for the first part of code for a while.
    – Rasty
    Mar 26, 2015 at 9:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.