生成概率树然后对结果进行排序的高效实现

Question

我有一些事件，其中每个事件都有发生的概率，如果发生则有一个权重。我想创建事件概率的所有可能组合以及相应的权重。最后，我需要将它们按重量顺序排序。这就像生成一棵概率树，但我只关心生成的叶子，而不关心获得它们所需的节点。我不需要在创建最终结果期间查找特定条目，只需创建所有值并按权重对它们进行排序。

只会有大约 5-15 个事件，但是由于 n 个事件有 2^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

Answer 1

50%是关于选择合适的数据结构，50%是关于算法。数据结构 - 我相信 TreeBidiMap将为你施展魔法。您需要实现 2 个比较器 - 1 个用于权重，另一个用于概率。
算法 - 微不足道。
祝你好运！

Answer 2

尝试加速代码的一些技巧：
- 尽量避免不必要的对象分配
- 尝试为您的集合使用正确的构造函数，在您的代码示例中，您似乎已经知道集合的大小，因此将其用作构造函数中的参数以防止无用的集合调整大小（和 gc 调用）
您可以尝试使用 Set 而不是 List，以便查看即时进行的排序......

HTH
杰罗姆