CODEWITHSUNDEEP
javaarraysrandom
xmen-5
xmen-5

Reputation: 1906

Peek at a value from an array with a probabilistic quantity

I have an array of 10 elements.

|1|2|3|4|5|6|7|8|9|10|

The idea is to randomly peek at a value from this array, but with some probabilistic quantity.

The probabilistic selection of the element is as follows:

|5%|10%|15%|30%|20%|4%|6%|1%|3%|6%|

This means that selecting the first element has a 5% chance, the second element has a 10% chance and so on.

My Solution:

import java.util.*;

public class Example {
     public static void main( String[] args ) {

         int [] values = {1,2,3,4,5,6,7,8,9,10};
         double [] probabilities = {0.05,0.1,0.15,0.3,0.2,0.04,0.06,0.01,0.03,0.06};


         double cumulativeSum = 0;
         double r = new Random().nextDouble();//random number between 0 and 1
         int index=0;// index of the chosen value
         for (double prob:probabilities) {
             cumulativeSum += prob;
             if (cumulativeSum >= r) {
                 break;
             }
             index++;
         }
         System.out.println(index);
         System.out.println("the value picked "+values[index]);

     }
}

I'm looking for a faster solution than mine. The array i made is only a tiny example, normally I can have arrays with 10000 cells.

Upvotes: 1

Views: 199

Answers (3)

Louis Wasserman
Louis Wasserman

Reputation: 198143

The alias method is an algorithm for the general problem of taking a set of probabilities for a number of possible values and precomputing some tables to be able to select an element with the specified probability distribution in O(1), instead of O(n). This is almost certainly the optimal algorithm for your use case.

Upvotes: 1

Soutzikevich
Soutzikevich

Reputation: 1031

It looks like you are implementing a type of Roulette Wheel Selection algorithm.

You can check this stack-overflow question for a detailed explanation of RWS.

As for the faster solution you're asking for, I don't think there would be a big increase in execution speed with some other algorithm. Your solution seems to be pretty fast and I can't see a reason why you would need something "faster". Code can always be optimized, but it depends on what you want to optimize and why you need something to be as fast as can be. If computational speed is critical in your situation, maybe consider implementing your code in Assembly, instead of Java.

There are other selection algorithms similar to RWS, like Stochastic Universal Selection (SUS), which would be more suited if you wanted to peek at more than one elements for example.

Upvotes: 2

Leo Aso
Leo Aso

Reputation: 12473

If your program uses those exact values (1-10), then it is rather trivial - just create an array where each entry appears multiple times according to its probability.

public static void main(String[] args) {
    int[] values = {
            1, 1, 1, 1, 1,
            2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
            3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
            4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
            4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
            5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
            5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
            6, 6, 6, 6,
            7, 7, 7, 7, 7, 7, 8, 9, 9, 9,
            10, 10, 10, 10, 10, 10, 10
    };

    int value = values[new Random().nextInt(values.length)];
    int index = value - 1; // values 1-10 are in indices 0-9

    System.out.println(index);
    System.out.println("the value picked " + value);
}

Like I said, this works for static values. If you have dynamic values, you'll need a different method.

Upvotes: 0

Related Questions