10

背景

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

有 4 个可能的Event对象ABCD。每个DataPoint都有 2 个,例如AC,除了集合中的第一个和最后一个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是一个DataPointhttp://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.pngf被调用两次,然后对于n-1 f之前的每个调用再次调用 两次,依此类推。O(2^n)考虑到DataPoints每个Set. 因为p()它独立于除参数之外的所有内容,所以我包含了一个缓存函数,如果p()已经对这些参数进行了计算,它只是返回之前的结果,但这并不能解决固有的复杂性问题。关于重复计算,我是否在这里遗漏了一些东西,或者这个算法中的复杂性是不可避免的?

4

3 回答 3

2

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

于 2012-08-15T15:03:18.670 回答
0

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;

    }
}
于 2012-08-15T15:30:19.423 回答
0

更新:

由于如下所述,不能使用顺序来帮助优化,因此必须使用另一种方法。由于大多数 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 是最好的表示)。

于 2012-08-15T11:32:37.700 回答