Эффективная по времени реализация генерации дерева вероятностей с последующей сортировкой результатов

У меня есть несколько событий, каждое из которых имеет вероятность произойти и вес, если они произойдут.Я хочу создать все возможные комбинации вероятностей событий с соответствующими весами. В конце концов, мне нужно отсортировать их по весу. Это похоже на создание дерева вероятностей, но меня интересуют только результирующие листья, а не то, какие узлы потребовались для их получения. Мне не нужно искать конкретные записи во время создания конечного результата, просто чтобы создать все значения и отсортировать их по весу.

Будет всего около 5-15 событий, но поскольку существует 2 ^ n возможных результатов с n событиями, а это нужно делать очень часто, я не хочу, чтобы это занимало излишне много времени. Скорость намного важнее, чем объем используемого хранилища.

Решение, которое я придумал, работает, но работает медленно. Есть идеи для более быстрого решения или идеи по улучшению?

   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
6
задан Siana 9 February 2012 в 16:22
поделиться