2

最初に疑似 C++ コードで私の状況を述べさせてください。

std:vector<double> sample(someFunctor f, double lower, double upper) {
    double t = (lower + upper)/2;
    double newval = f(t);

    if (f(upper) - newval > epsilon)
        subsample1 = sample(f, t, upper);
    if (newval - f(lower) > epsilon)
        subsample2 = sample(f, lower, t);

    return concat(subsample2, newval, subsample1);
}

ここで、concat は返されたベクトルを連結します。基本的に、保存された 2 つの関数値の間にわずかな違いしかないような方法で関数をサンプリングしています。

すべての再帰ステップでかなりの量のメモリ割り当て (2 つのサブベクトルを割り当ててから、それらと別の要素を連結) があるように見えるため、上記の方法には満足できません。そのコードは、パフォーマンスに関して重要なアルゴリズムの一部で実行する必要があります。upper - lowerかなり小さい場合は、評価にfそれほど時間はかかりません。

だから私の質問：

  • すべての再帰呼び出しで同じデータ構造を使用し、そのベクトルの現在の部分を埋めるだけの巧妙な方法を見つけましたか? (必要な関数評価の数は前もってわからないことに注意してください)。これについての考え：

    • ベクトルの代わりにリストを使用します。しかし、ダブルを格納するだけでは、メモリのオーバーホールは十分ではないと感じています。
    • ベクトルの穴を保持し、どのエントリが埋められるかを示す別のベクトルを維持します。subsample再帰呼び出しの最後で、と の間に穴がないようにエントリをシフトしますnewval。しかし今、2番目のベクトルの追加作業でシフトすることでコピーを切り替えます-おそらく悪い考えです。

  • 再帰を完全に取り除く方法はありますか? ただし、正確さのために、上記の分割統治パターンを使用することが重要です。この関数fは上限と下限を多用し、これによってかなりのパフォーマンスが得られます。

ご感想ありがとうございます。

Space_C0wb0y の要求に従って、私の問題を言い換えてみます。おそらく最初の説明はあまり明確ではありませんでした。

特定の間隔でサンプリングする（たとえば、特定のポイントで評価する）関数（数学的な意味で）があります。

間隔が [0,100] であるとします。f(0)=0関数の値が 0と100 であることはわかっていますf(100) = 40。ここで、間隔の中間点である 50 で関数を評価します。たとえば、関数が を返しますf(50)=10。としてf(0)-f(50) <= 10、間隔 [0,50] にこれ以上のサンプルは必要ありません。ただし、間隔 [50,100] についてはさらに計算が必要です。したがって、次の (再帰的な) ステップで を評価しf(75)ます。上記のロジックを再帰的に繰り返します。

最後に、次のような対応するパラメーターを持つ関数値を提供する (2 つの) ベクトルを使用したいと思います。

parameter  = vector(0, 50, 56.25, 62.5, 75, 100)
value      = vector(0, 10, 17.21, 25    34,  40)

これらのベクトルを再帰的に構築するための最良の（最もパフォーマンスの高い）アプローチを探しています。

これが物事を明確にすることを願っています。

4

3 に答える 3

2

スペースは重要な問題ではないので、再帰を使用し続けます。

1. (戻り) 値によるコピーではなく、参照によるコピーを使用します。

2. 定数であるため、ファンクターを渡す必要はありません。

3.lowとhighが整数であれば、より高速であった可能性があります。ただし、要件によって異なります。

    // Thanks to Space_C0wb0y, here we avoid using a global vector
    // by passing the vector as reference. It's efficient as there
    // is no copy overhead as well.        
    void sample(vector<double>& samples, double low, double high)
    {
       // You can use shift operator if they're integers.
       double mid = (low + high)/2;

       // Since they're double, you need prevent them from being too close.
       // Otherwise, you'll probably see stack overflow.
       // Consider this case:
       // f(x): x=1, 0<x<8;  x*x, x<=0 or x>=8
       // low = 1, high = 10, epsilon = 10
       if (high - low < 0.5)
       {
          samples.push_back(f(mid));
          return;
       }   

       // The order you write the recursive calls guarantees you
       // the sampling order is from left to right.
       if (f(mid) - f(low) > epsilon)
       {
          sample(samples, low, mid);
       }

       samples.push_back(f(mid));

       if (f(high) - f(mid) > epsilon)
       {
          sample(samples, mid, high);
       }   
    }
于 2011-06-15T09:26:17.520 に答える
1

次のアプローチをお勧めします。

  1. 2 つのベクトルを使用するのではなく、ペアを持つ 1 つのベクトルまたはカスタムstructを使用してパラメーターと値を表します。

    struct eval_point {
    double parameter;
    double value;
};

std::vector<eval_point> evaluated_points;

  2. アルゴリズムを変更して、評価の結果を出力反復子に書き込みます。

    template<class F, class output_iterator_type>
void sample(F someFunctor, double lower, double upper,
            output_iterator_type out) {
    double t = (lower + upper)/2;
    eval_point point = { t, f(t) };

    if (f(upper) - point.value > epsilon) {
        *out = point;
        ++out;
        sample(f, t, upper, out);
    }
    if (point.value - f(lower) > epsilon) {
        *out = point;
        ++out;
        subsample2 = sample(f, lower, t, out);
    }
}

    上記は、出力反復子を使用した場合にどのように見えるかを示す疑似コードの変更です。テストしていないので、正しいかどうかはわかりません。原則として、次のように呼び出します。

    std::vector<eval_point> results;
sample(someFunction, 0, 100, std::back_inserter<eval_point>(results));

    これにより、再帰呼び出しごとに新しいベクトルを作成する必要がなくなります。サンプル数の妥当な下限を推測できる場合は、再割り当てが不要になるように事前割り当てできる可能性があります。その場合、次のように呼び出します。

    std::vector<eval_point> results(lower_bound_for_samples);
sample(someFunction, 0, 100, results.begin());

次に、生成されたサンプルの数を追跡するために、追加のカウンターを追加する必要があります。

于 2011-06-15T09:15:52.020 に答える
0

リストソリューションを拒否する理由がわかりません。最悪のケースは、リストのサイズが生データの 3 倍になることです。これは、関数呼び出しごとに新しいベクトルを作成する場合よりもはるかに少ないと思います。両者のインターフェースはほぼ同じなので、それほど大きな変更は必要ありませんので、試してみてください。

于 2011-06-15T08:05:23.150 に答える