java - Javaでの再帰的アルゴリズムの最適化

Question

バックグラウンド

順序付けられたデータポイントのセットがとして保存されていTreeSet<DataPoint>ます。各データポイントには、apositionとaSetのEventオブジェクト（HashSet<Event>）があります。

4つの可能なEventオブジェクト、、、、AおよびがありBます。サイズが1であるセットの最初と最後のオブジェクトを除いて、すべてにこれらの2つがあります（例：と）。CDDataPointACDataPointT

私のアルゴリズムは、このセットDataPoint Qにある位置xに新しいものがある確率を見つけることです。Event q

これを行うには、このデータセットの値Sを計算してから、セットに追加Qして再度計算Sします。次に、2番目を1番目で割って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.pngDataPointはセットの最後（右側のノード）、 http：//mathbin.net/equations/105225_8.pngは最初DataPoint（左側のノード）、http：//mathbin.net/equations/105225_9 .pngDataPointはノードではない右端、 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)
    }
}

したがって、での確率を見つけるQにxはq：

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

問題

現時点での実装は、数学アルゴリズムに厳密に従っています。ただし、これは実際には特に良いアイデアではないことがわかります。これfは、それぞれに対して2回呼び出されるためDataPointです。したがって、http：//mathbin.net/equations/105225_9.pngの場合、fは2回呼び出され、その後n-1 f、前の呼び出しごとに2回呼び出され、以下同様に続きます。これは、それぞれに1000を超える可能性があることを考えると、その複雑さO(2^n)はかなりひどいものになります。パラメータ以外のすべてから独立しているため、キャッシュ関数を含めました。DataPointsSetp()p()これらのパラメータについてはすでに計算されており、前の結果を返すだけですが、これは固有の複雑さの問題を解決しません。繰り返しの計算に関してここで何かが欠けていますか、それともこのアルゴリズムの複雑さは避けられませんか？

score 2 · Accepted Answer

また、最初の2つの引数についてメモ化する必要がありfます（3つ目は常に渡されるため、心配する必要はありません）。これにより、コードの時間計算量がO（2 ^ n）からO（n）に減少します。

score 0 · Accepted Answer

すべての提案をありがとう。Pの値とFすでに計算された値に対して新しいネストされたクラスを作成HashMapし、結果を格納するためにを使用して、ソリューションを実装しました。次にHashMap、計算が行われる前に、結果が照会されます。存在する場合は結果を返すだけで、存在しない場合は結果を計算してに追加しHashMapます。

最終的な製品は次のようになります。

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値は複数回計算されるため（前述のように、これはコストがかかります）、1つの最適化はそれらをキャッシュすることです。最適なキーが何であるかはわかりませんが、コードを次のように変更することを想像できます。

....
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;
}

このアプローチは、冗長な計算の多くを効果的に減らすはずです-しかし、あなたは私よりもはるかに多くのデータを知っているので、キーを設定するための最良の方法を決定する必要があります（そして文字列がそのための最良の表現であるとしても）。

java - Javaでの再帰的アルゴリズムの最適化

バックグラウンド

アルゴリズム

実装

問題

3 に答える 3

Related

Reference