Efficient temporary implementation of probability tree generation and then sorting the results

Question

I have some events where each of them has a chance to occur, and weight, if they do. I want to create all possible combinations of event probabilities with corresponding weights. In the end, I need them in order of weight. This is similar to generating a probability tree, but I only care about the leaves received, and not about which nodes he took to get them. I don’t need to look for specific records while creating the final result, just to create all the values ​​and sort them by weight.

There will be only about 5-15 events, but since there are 2 ^ n resulting opportunities with n events, and this needs to be done very often, I do not want this to take too much time. Speed ​​is much more important than the amount of storage used.

The solution I came up with is slow but slow. Any idea for a quicker solution or some ideas for improvement?

class ProbWeight { double prob; double eventWeight; public ProbWeight(double aProb, double aeventWeight) { prob = aProb; eventWeight = aeventWeight; } public ProbWeight(ProbWeight aCellProb) { prob = aCellProb.getProb(); eventWeight = aCellProb.geteventWeight(); } public double getProb(){ return prob; } public double geteventWeight(){ return eventWeight; } public void doesHappen(ProbWeight aProb) { prob*=aProb.getProb(); eventWeight += aProb.geteventWeight(); } public void doesNotHappen(ProbWeight aProb) { prob*=(1-aProb.getProb()); } } //Data generation for testing List<ProbWeight> dataList = new ArrayList<ProbWeight>(); for (int i =0; i<5; i++){ ProbWeight prob = new ProbWeight(Math.random(), 10*Math.random(), i); dataList.add(prob); } //The list where the results will end up List<ProbWeight> resultingProbList = new ArrayList<ProbWeight>(); // a temporaty list to avoid modifying a list while looping through it List<ProbWeight> tempList = new ArrayList<ProbWeight>(); resultingProbList.add(dataList.remove(0)); for (ProbWeight data : dataList){ //for each event //go through the already created event combinations and create two new for each for(ProbWeight listed: resultingProbList){ ProbWeight firstPossibility = new ProbWeight(listed); ProbWeight secondPossibility = new ProbWeight(listed); firstPossibility.doesHappen(data); secondPossibility.doesNotHappen(data); tempList.add(firstPossibility); tempList.add(secondPossibility); } resultingProbList = new ArrayList<ProbWeight>(tempList); } // Then sort the list by weight using sort and a comparator 

Answer 1

This is 50% of the choice of the corresponding data structure and 50% of the algorithm. Data structure - I believe TreeBidiMap will do the magic for you. You will need to implement 2 comparators - 1 for weight and another for probability. The algorithm is trivial. Good luck

Answer 2

just a few tricks to try to speed up your code: - try to avoid highlighting unnecessary objects - try using the correct constructor for your collections, in your code example it seems that you already know the size of the collections, so use it as a parameter in the constructors to prevent resizing useless collections (and gc calls) You can try using a set instead of a list to see an order made on the fly .....

NTN Jerome