java - Java中递归算法的优化

Question

背景

我有一组有序的数据点存储为TreeSet<DataPoint>. 每个数据点都有一个position和一个Set对象Event( HashSet<Event>)。

有 4 个可能的Event对象A、B、C和D。每个DataPoint都有 2 个，例如A和C，除了集合中的第一个和最后一个DataPoint对象，它们T的大小为 1。

我的算法是在这个集合中找到一个新DataPoint Q位置x的概率。Event q

我通过计算S这个数据集的值，然后添加Q到集合中并S再次计算来做到这一点。然后我将第二个S除以第一个以隔离新的概率DataPoint Q。

算法

计算公式为S：

http://mathbin.net/equations/105225_0.png

在哪里

http://mathbin.net/equations/105225_1.png

http://mathbin.net/equations/105225_2.png

对于 http://mathbin.net/equations/105225_3.png

和

http://mathbin.net/equations/105225_4.png

http://mathbin.net/equations/105225_5.png是一个昂贵的概率函数，它只依赖于它的参数而不依赖于其他任何东西（和http://mathbin.net/equations/105225_6.png），http://mathbin。 net/equations/105225_7.png是集合中的最后一个DataPoint（右手节点），http ://mathbin.net/equations/105225_8.png 是第一个DataPoint（左手节点），http ://mathbin.net/equations/105225_9 .png是最右边DataPoint的不是节点，http ://mathbin.net/equations/105225_10.png是一个DataPoint，http://mathbin.net/equations/105225_12.png是这个Set的事件DataPoint。

所以Qwith的概率Event q是：

http://mathbin.net/equations/105225_11.png

执行

我在Java中实现了这个算法，如下所示：

public class ProbabilityCalculator {
    private Double p(DataPoint right, Event rightEvent, DataPoint left, Event leftEvent) {
        // do some stuff
    }
    
    private Double f(DataPoint right, Event rightEvent, NavigableSet<DataPoint> points) {
        DataPoint left = points.lower(right);
        
        Double result = 0.0;
        
        if(left.isLefthandNode()) {
            result = 0.25 * p(right, rightEvent, left, null);
        } else if(left.isQ()) {
            result = p(right, rightEvent, left, left.getQEvent()) * f(left, left.getQEvent(), points);
        } else { // if M_k
            for(Event leftEvent : left.getEvents())
                result += p(right, rightEvent, left, leftEvent) * f(left, leftEvent, points);
        }
        
        return result;
    }
    
    public Double S(NavigableSet<DataPoint> points) {
        return f(points.last(), points.last().getRightNodeEvent(), points)
    }
}

所以要找到Qatx的概率q：

Double S1 = S(points);
points.add(Q);
Double S2 = S(points);
Double probability = S2/S1;

问题

就目前的实现而言，它严格遵循数学算法。然而，这在实践中并不是一个特别好的主意，因为f每个DataPoint. 因此，对于http://mathbin.net/equations/105225_9.png，f被调用两次，然后对于n-1 f之前的每个调用再次调用两次，依此类推。O(2^n)考虑到DataPoints每个Set. 因为p()它独立于除参数之外的所有内容，所以我包含了一个缓存函数，如果p()已经对这些参数进行了计算，它只是返回之前的结果，但这并不能解决固有的复杂性问题。关于重复计算，我是否在这里遗漏了一些东西，或者这个算法中的复杂性是不可避免的？

score 2 · Accepted Answer

您还需要记住f前 2 个参数（第 3 个参数始终通过，因此您无需担心）。这会将代码的时间复杂度从 O(2^n) 降低到 O(n)。

score 0 · Accepted Answer

Thanks for all your suggestions. I implemented my solution by creating new nested classes for the values of P and F already calculated, then used a HashMap to store the results. The HashMap is then queried for the result before computation takes place; if it is present it just returns the result, if it is not it computes the result and adds it to the HashMap.

The final product looks a bit like this:

public class ProbabilityCalculator {

    private NavigableSet<DataPoint> points;

    private ProbabilityCalculator(NavigableSet<DataPoint> points) {
        this.points = points;
    }

    private static class P {
        public final DataPoint left;
        public final Event leftEvent;
        public final DataPoint right;
        public final Event rightEvent;

        public P(DataPoint left, Event leftEvent, DataPoint right, Event rightEvent) {
            this.left = left;
            this.leftEvent = leftEvent;
            this.right = right;
            this.rightEvent = rightEvent;
        }

        public boolean equals(Object o) {
            if(!(o instanceof P)) return false;
            P p = (P) o;

            if(!(this.leftEvent == null ? p.leftEvent == null : this.leftEvent.equals(p.leftEvent)))
                return false;
            if(!(this.rightEvent == null ? p.rightEvent == null : this.rightEvent.equals(p.rightEvent)))
                return false;

            return this.left.equals(p.left) && this.right.equals(p.right);
        }

        public int hashCode() {
            int result = 93;

            result = 31 * result + this.left.hashCode();
            result = 31 * result + this.right.hashCode();
            result = this.leftEvent != null ? 31 * result + this.leftEvent.hashCode() : 31 * result;
            result = this.rightEvent != null ? 31 * result + this.rightEvent.hashCode() : 31 * result;

            return result;
        }
    }

    private Map<P, Double> usedPs = new HashMap<P, Double>();

    private static class F {
        public final DataPoint left;
        public final Event leftEvent;
        public final NavigableSet<DataPoint> dataPointsToLeft;

        public F(DataPoint dataPoint, Event dataPointEvent, NavigableSet<DataPoint> dataPointsToLeft) {
            this.dataPoint = dataPoint;
            this.dataPointEvent = dataPointEvent;
            this.dataPointsToLeft = dataPointsToLeft;
        }

        public boolean equals(Object o) {
            if(!(o instanceof F)) return false;
            F f = (F) o;
            return this.dataPoint.equals(f.dataPoint) && this.dataPointEvent.equals(f.dataPointEvent) && this.dataPointsToLeft.equals(f.dataPointsToLeft);
        }

        public int hashCode() {
            int result = 7;

            result = 31 * result + this.dataPoint.hashCode();
            result = 31 * result + this.dataPointEvent.hashCode();
            result = 31 * result + this.dataPointsToLeft.hashCode();

            return result;
        }

    }

    private Map<F, Double> usedFs = new HashMap<F, Double>();

    private Double p(DataPoint right, Event rightEvent, DataPoint left, Event leftEvent) {
        P newP = new P(right, rightEvent, left, leftEvent);

        if(this.usedPs.containsKey(newP)) return usedPs.get(newP);


        // do some stuff

        usedPs.put(newP, result);
        return result;

    }

    private Double f(DataPoint right, Event rightEvent) {

        NavigableSet<DataPoint> dataPointsToLeft = dataPoints.headSet(right, false);

        F newF = new F(right, rightEvent, dataPointsToLeft);

        if(usedFs.containsKey(newF)) return usedFs.get(newF);

        DataPoint left = points.lower(right);

        Double result = 0.0;

        if(left.isLefthandNode()) {
            result = 0.25 * p(right, rightEvent, left, null);
        } else if(left.isQ()) {
            result = p(right, rightEvent, left, left.getQEvent()) * f(left, left.getQEvent(), points);
        } else { // if M_k
            for(Event leftEvent : left.getEvents())
                result += p(right, rightEvent, left, leftEvent) * f(left, leftEvent, points);
        }

        usedFs.put(newF, result)

        return result;
    }

    public Double S() {
        return f(points.last(), points.last().getRightNodeEvent(), points)
    }

    public static probabilityOfQ(DataPoint q, NavigableSet<DataPoint> points) {
        ProbabilityCalculator pc = new ProbabilityCalculator(points);

        Double S1 = S();

        points.add(q);

        Double S2 = S();

        return S2/S1;

    }
}

score 0 · Accepted Answer

更新：

由于如下所述，不能使用顺序来帮助优化，因此必须使用另一种方法。由于大多数 P 值将被计算多次（并且如上所述，这很昂贵），因此一种优化是缓存它们。我不确定最好的密钥是什么，但您可以想象更改代码如下：

....
private Map<String, Double> previousResultMap = new ....


private Double p(DataPoint right, Event rightEvent, DataPoint left, Event leftEvent) {
   String key = // calculate unique key from inputs
   Double previousResult = previousResultMap.get(key);
   if (previousResult != null) {
      return previousResult;
   } 

   // do some stuff
   previousResultMap.put(key, result);
   return result;
}

这种方法应该可以有效地减少大量冗余计算 - 但是，由于您比我更了解数据，因此您需要确定设置密钥的最佳方式（即使 String 是最好的表示）。

java - Java中递归算法的优化

背景

算法

执行

问题

3 回答 3

Related

Reference