背景
我有一组有序的数据点存储为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
。
所以Q
with的概率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)
}
}
所以要找到Q
atx
的概率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()
已经对这些参数进行了计算,它只是返回之前的结果,但这并不能解决固有的复杂性问题。关于重复计算,我是否在这里遗漏了一些东西,或者这个算法中的复杂性是不可避免的?