Percentage random branching coding pattern?

Question

So, let's say we have a block of code that we want to execute 70% times and another 30% times.

if(Math.random() < 0.7) 70percentmethod(); else 30percentmethod(); 

Simple enough. But what if we want it to be easily extensible to say 30% / 60% / 10%, etc.? Here it would be necessary to add and modify all if statements that are not very convenient to use, slow and error-prone.

So far, I have found great keys for decent use for this use case, for example:

 switch(rand(0, 10)){ case 0: case 1: case 2: case 3: case 4: case 5: case 6: case 7:70percentmethod();break; case 8: case 9: case 10:30percentmethod();break; } 

Which can be very easily changed to:

 switch(rand(0, 10)){ case 0:10percentmethod();break; case 1: case 2: case 3: case 4: case 5: case 6: case 7:60percentmethod();break; case 8: case 9: case 10:30percentmethod();break; } 

But they also have their own shortcomings, bulky and divided into a predetermined number of divisions.

Something ideal would be based on a "frequency number" system, I think, like this:

 (1,a),(1,b),(2,c) -> 25% a, 25% b, 50% c 

then if you added one more:

 (1,a),(1,b),(2,c),(6,d) -> 10% a, 10% b, 20% c, 60% d 

This way, just adding numbers, making the sum equal to 100%, and then divide it.

I suppose it would not be easy to make a handler for it using a configured hash map or something like that, but I am wondering if there is some established method / template or lambda for it before I go for all the spaghetti .

Answer 1

EDIT: See the end for more elegant solutions. I will leave it though.

You can use NavigableMap to store these methods associated with their percentages.

 NavigableMap<Double, Runnable> runnables = new TreeMap<>(); runnables.put(0.3, this::30PercentMethod); runnables.put(1.0, this::70PercentMethod); public static void runRandomly(Map<Double, Runnable> runnables) { double percentage = Math.random(); for (Map.Entry<Double, Runnable> entry : runnables){ if (entry.getKey() < percentage) { entry.getValue().run(); return; // make sure you only call one method } } throw new RuntimeException("map not filled properly for " + percentage); } // or, because I'm still practicing streams by using them for everything public static void runRandomly(Map<Double, Runnable> runnables) { double percentage = Math.random(); runnables.entrySet().stream() .filter(e -> e.getKey() < percentage) .findFirst().orElseThrow(() -> new RuntimeException("map not filled properly for " + percentage)) .run(); } 

NavigableMap sorted (for example, HashMap does not give any guarantees for entries) with keys, so you get entries sorted by their percentage. This is important because if you have two elements (3, r1), (7, r2), they lead to the following entries: r1 = 0.3 and r2 = 1.0 , and they need to be evaluated in this order (for example, if they evaluated in reverse order the result will always be r2 ).

As for splitting, it should look something like this: With a Tuple class like this

 static class Pair<X, Y> { public Pair(X f, Y s) { first = f; second = s; } public final X first; public final Y second; } 

You can create such a map

 // the parameter contains the (1,m1), (1,m2), (3,m3) pairs private static Map<Double,Runnable> splitToPercentageMap(Collection<Pair<Integer,Runnable>> runnables) { // this adds all Runnables to lists of same int value, // overall those lists are sorted by that int (so least probable first) double total = 0; Map<Integer,List<Runnable>> byNumber = new TreeMap<>(); for (Pair<Integer,Runnable> e : runnables) { total += e.first; List<Runnable> list = byNumber.getOrDefault(e.first, new ArrayList<>()); list.add(e.second); byNumber.put(e.first, list); } Map<Double,Runnable> targetList = new TreeMap<>(); double current = 0; for (Map.Entry<Integer,List<Runnable>> e : byNumber.entrySet()) { for (Runnable r : e.getValue()) { double percentage = (double) e.getKey() / total; current += percentage; targetList.put(current, r); } } return targetList; } 

And all this is added to the class

 class RandomRunner { private List<Integer, Runnable> runnables = new ArrayList<>(); public void add(int value, Runnable toRun) { runnables.add(new Pair<>(value, toRun)); } public void remove(Runnable toRemove) { for (Iterator<Pair<Integer, Runnable>> r = runnables.iterator(); r.hasNext(); ) { if (toRemove == r.next().second) { r.remove(); break; } } } public void runRandomly() { // split list, use code from above } } 

EDIT:
Actually, the above is what you get if your idea is stuck in your head and do not question its correctness. Keeping the interface of the RandomRunner class is a lot simpler:

 class RandomRunner { List<Runnable> runnables = new ArrayList<>(); public void add(int value, Runnable toRun) { // add the methods as often as their weight indicates. // this should be fine for smaller numbers; // if you get lists with millions of entries, optimize for (int i = 0; i < value; i++) { runnables.add(toRun); } } public void remove(Runnable r) { Iterator<Runnable> myRunnables = runnables.iterator(); while (myRunnables.hasNext()) { if (myRunnables.next() == r) { myRunnables.remove(); } } public void runRandomly() { if (runnables.isEmpty()) return; // roll n-sided die int runIndex = ThreadLocalRandom.current().nextInt(0, runnables.size()); runnables.get(runIndex).run(); } } 

Answer 2

All of these answers seem rather complicated, so I will just post a simple option:

 double rnd = Math.random() if((rnd -= 0.6) < 0) 60percentmethod(); else if ((rnd -= 0.3) < 0) 30percentmethod(); else 10percentmethod(); 

No need to change other lines, and you can easily see what happens without digging into the helper classes. A slight drawback is that it does not ensure that percentages are 100%.

Answer 3

I'm not sure if there is a common name for this, but I think I recognized it as a wheel of luck at the university.

Basically, it works the way you described: it gets a list of values ​​and "frequency numbers", and one is selected according to weighted probabilities.

 list = (1,a),(1,b),(2,c),(6,d) total = list.sum() rnd = random(0, total) sum = 0 for i from 0 to list.size(): sum += list[i] if sum >= rnd: return list[i] return list.last() 

A list can be a parameter of a function if you want to generalize this.

This also works with floating point numbers, and the numbers do not need to be normalized. If you normalize (for example, to 1), you can skip the list.sum() .

EDIT:

In connection with the requirement, an actual compilation example of Java implementation and use is presented here:

 import java.util.ArrayList; import java.util.Random; public class RandomWheel<T> { private static final class RandomWheelSection<T> { public double weight; public T value; public RandomWheelSection(double weight, T value) { this.weight = weight; this.value = value; } } private ArrayList<RandomWheelSection<T>> sections = new ArrayList<>(); private double totalWeight = 0; private Random random = new Random(); public void addWheelSection(double weight, T value) { sections.add(new RandomWheelSection<T>(weight, value)); totalWeight += weight; } public T draw() { double rnd = totalWeight * random.nextDouble(); double sum = 0; for (int i = 0; i < sections.size(); i++) { sum += sections.get(i).weight; if (sum >= rnd) return sections.get(i).value; } return sections.get(sections.size() - 1).value; } public static void main(String[] args) { RandomWheel<String> wheel = new RandomWheel<String>(); wheel.addWheelSection(1, "a"); wheel.addWheelSection(1, "b"); wheel.addWheelSection(2, "c"); wheel.addWheelSection(6, "d"); for (int i = 0; i < 100; i++) System.out.print(wheel.draw()); } } 

Answer 4

While the selected answer works, it is unfortunately asymptotically slow for your use case. Instead, you can use something called Alias ​​Sampling . A sampling algorithm (or alias) is a method used to select items with a weighted distribution. If the selection weights of these elements do not change, you can make a selection within O (1) !. If this is not the case, you can get the amortized time O (1) if the ratio between the number of options you choose and the changes you make to the alias table (change weights) are high. The currently selected answer is offered by the O (N) algorithm, the next best thing is O (log (N)) taking into account the sorted probabilities and a binary search , but nothing will beat the O (1) time that I suggested.

This site provides a good overview of the alias method, which is mainly a language agnostic. Essentially, you create a table in which each record represents the result of two probabilities. There is one threshold for each record in the table, below the threshold you get one value, above you get a different value. You distribute high probabilities into several table values ​​to create a probability graph with an area of ​​one for all probabilities.

Say you have probabilities A, B, C, and D, which have values ​​of 0.1, 0.1, 0.1, and 0.7, respectively. The alias method would spread the probability of 0.7 for everyone else. One index will correspond to each probability, where you will have 0.1 and 0.15 for ABC and 0.25 for index D. At the same time, you normalize each probability so that you get 0.4 probability to get probability A and 0.6, so that get D in index A (0,1 / (0,1 + 0,15) and 0,15 / (0,1 + 0,15) respectively), as well as B and C index and 100% probability to get index D in D (0.25 / 0.25 is 1).

Given the unbiased unified PRNG (Math.Random ()) for indexing, you get an equal probability of choosing each index, but you also flip coins for each index, which provides a weighted probability. You have a 25% chance of landing on slot A or D, but in this case you have only a 40% chance of dialing A and 60% D..40 * .25 * .25 = 0.1, our initial probability, and if you add all the probabilities D scattered by other indices, you will get .70 again.

To make a random selection, you only need to create a random index from 0 to N, and then make a coin flip, no matter how many items you add, this is a very fast and constant cost. Creating an alias table doesn’t take too many lines of code, my python version takes 80 lines, including import statements and line breaks, and the version presented in the Pandas article is the same size (and this is C ++)

For your java implementation, you can correlate the probabilities and indices of the list of arrays with your functions that you must perform by creating an array of functions that are executed when each of them is indexed, you can also use function objects ( functors ), which have a method that you use to passing parameters to execute.

 ArrayList<(YourFunctionObject)> function_list; // add functions AliasSampler aliassampler = new AliasSampler(listOfProbabilities); // somewhere later with some type T and some parameter values. int index = aliassampler.sampleIndex(); T result = function_list[index].apply(parameters); 

EDIT:

I created a version in java of the AliasSampler method using classes, this uses an example index method and should be able to be used as described above.

 import java.util.ArrayList; import java.util.Collections; import java.util.Random; public class AliasSampler { private ArrayList<Double> binaryProbabilityArray; private ArrayList<Integer> aliasIndexList; AliasSampler(ArrayList<Double> probabilities){ // java 8 needed here assert(DoubleStream.of(probabilities).sum() == 1.0); int n = probabilities.size(); // probabilityArray is the list of probabilities, this is the incoming probabilities scaled // by the number of probabilities. This allows us to figure out which probabilities need to be spread // to others since they are too large, ie [0.1 0.1 0.1 0.7] = [0.4 0.4 0.4 2.80] ArrayList<Double> probabilityArray; for(Double probability : probabilities){ probabilityArray.add(probability); } binaryProbabilityArray = new ArrayList<Double>(Collections.nCopies(n, 0.0)); aliasIndexList = new ArrayList<Integer>(Collections.nCopies(n, 0)); ArrayList<Integer> lessThanOneIndexList = new ArrayList<Integer>(); ArrayList<Integer> greaterThanOneIndexList = new ArrayList<Integer>(); for(int index = 0; index < probabilityArray.size(); index++){ double probability = probabilityArray.get(index); if(probability < 1.0){ lessThanOneIndexList.add(index); } else{ greaterThanOneIndexList.add(index); } } // while we still have indices to check for in each list, we attempt to spread the probability of those larger // what this ends up doing in our first example is taking greater than one elements (2.80) and removing 0.6, // and spreading it to different indices, so (((2.80 - 0.6) - 0.6) - 0.6) will equal 1.0, and the rest will // be 0.4 + 0.6 = 1.0 as well. while(lessThanOneIndexList.size() != 0 && greaterThanOneIndexList.size() != 0){ //https://stackoverflow.com/questions/16987727/removing-last-object-of-arraylist-in-java // last element removal is equivalent to pop, java does this in constant time int lessThanOneIndex = lessThanOneIndexList.remove(lessThanOneIndexList.size() - 1); int greaterThanOneIndex = greaterThanOneIndexList.remove(greaterThanOneIndexList.size() - 1); double probabilityLessThanOne = probabilityArray.get(lessThanOneIndex); binaryProbabilityArray.set(lessThanOneIndex, probabilityLessThanOne); aliasIndexList.set(lessThanOneIndex, greaterThanOneIndex); probabilityArray.set(greaterThanOneIndex, probabilityArray.get(greaterThanOneIndex) + probabilityLessThanOne - 1); if(probabilityArray.get(greaterThanOneIndex) < 1){ lessThanOneIndexList.add(greaterThanOneIndex); } else{ greaterThanOneIndexList.add(greaterThanOneIndex); } } //if there are any probabilities left in either index list, they can't be spread across the other //indicies, so they are set with probability 1.0. They still have the probabilities they should at this step, it works out mathematically. while(greaterThanOneIndexList.size() != 0){ int greaterThanOneIndex = greaterThanOneIndexList.remove(greaterThanOneIndexList.size() - 1); binaryProbabilityArray.set(greaterThanOneIndex, 1.0); } while(lessThanOneIndexList.size() != 0){ int lessThanOneIndex = lessThanOneIndexList.remove(lessThanOneIndexList.size() - 1); binaryProbabilityArray.set(lessThanOneIndex, 1.0); } } public int sampleIndex(){ int index = new Random().nextInt(binaryProbabilityArray.size()); double r = Math.random(); if( r < binaryProbabilityArray.get(index)){ return index; } else{ return aliasIndexList.get(index); } } } 

Answer 5

You can calculate the cumulative probability for each class, choose a random number from [0; 1) and see where this number falls.

 class WeightedRandomPicker { private static Random random = new Random(); public static int choose(double[] probabilties) { double randomVal = random.nextDouble(); double cumulativeProbability = 0; for (int i = 0; i < probabilties.length; ++i) { cumulativeProbability += probabilties[i]; if (randomVal < cumulativeProbability) { return i; } } return probabilties.length - 1; // to account for numerical errors } public static void main (String[] args) { double[] probabilties = new double[]{0.1, 0.1, 0.2, 0.6}; // the final value is optional for (int i = 0; i < 20; ++i) { System.out.printf("%d\n", choose(probabilties)); } } } 

Answer 6

The following is a bit like @daniu's answer, but uses the methods provided by TreeMap :

 private final NavigableMap<Double, Runnable> map = new TreeMap<>(); { map.put(0.3d, this::branch30Percent); map.put(1.0d, this::branch70Percent); } private final SecureRandom random = new SecureRandom(); private void branch30Percent() {} private void branch70Percent() {} public void runRandomly() { final Runnable value = map.tailMap(random.nextDouble(), true).firstEntry().getValue(); value.run(); } 

Thus, there is no need to TreeSet over the entire map until the corresponding record is found, but the TreeSet features are TreeSet when searching for the record with a key specially compared with another key. This, however, will only matter if the number of entries on the map is large. However, it saves a few lines of code.

Answer 7

I would do something like this:

 class RandomMethod { private final Runnable method; private final int probability; RandomMethod(Runnable method, int probability){ this.method = method; this.probability = probability; } public int getProbability() { return probability; } public void run() { method.run(); } } class MethodChooser { private final List<RandomMethod> methods; private final int total; MethodChooser(final List<RandomMethod> methods) { this.methods = methods; this.total = methods.stream().collect( Collectors.summingInt(RandomMethod::getProbability) ); } public void chooseMethod() { final Random random = new Random(); final int choice = random.nextInt(total); int count = 0; for (final RandomMethod method : methods) { count += method.getProbability(); if (choice < count) { method.run(); return; } } } } 

Sample Usage:

 MethodChooser chooser = new MethodChooser(Arrays.asList( new RandomMethod(Blah::aaa, 1), new RandomMethod(Blah::bbb, 3), new RandomMethod(Blah::ccc, 1) )); IntStream.range(0, 100).forEach( i -> chooser.chooseMethod() ); 

Run it here .