Time efficient implementation of generating probability tree and then sorting the results

Question

I have some events, where each of them has a probability to happen, and a weight if they do. I want to create all possible combinations of probabilities of events, with the corresponding weights. In the end, I need them sorted in weight order. It is like generating a probability tree, but I only care about the resulting leaves, not which nodes it took to get them. I don't need to look up specific entries during the creation of the end result, just to create all the values and sort them by weight.

There will be only about 5-15 events,but since there is 2^n resulting possibilities with n events, and this is to be done very often, I don’t want it to take unnecessarily long time. Speed is much more important than the amount of storage used.

The solution I came up with works but is 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

It is 50% about choosing an appropriate data structure and 50% about the algorithm. Data structure - I believe TreeBidiMap will do the magic for you. You will need to implement 2 Comparators - 1 for the weight and another for the probability. Algorithm - trivial. Good luck!

Answer 2

just a few tricks to try to speed up your code: - try to avoid non necessary objects allocation - try to use the right constructor for your collections , in your code sample it seems that you already know the size of the collections, so use it as a parameter in the constructors to prevent useless collections resizing (and gc calls) You may try to use a Set instead of List in order to see the ordering made on the fly.....

HTH jerome