0

すべての再帰関数を反復バージョンに変換できることを知っています。誰かがこの擬似コードの反復バージョンを見つけるのを手伝ってくれますか? コードを最適化しようとしていますが、再帰は明らかに適していません

sub calc (a, b )
{
    total = 0;
    if(b <= 1) 
        return 1
    if( 2*a > CONST)
        for i IN (1..CONST)
            total += calc(i, b-1) ;
    else
        for j IN (2*a..CONST)
            total += calc(j, b-1) ;
    return total;
}
CONST = 100;
print calc (CONST,2000);

助けてくれてありがとう！

4

2 に答える 2

2

再帰から反復へのリファクタリングは、ここでのパフォーマンスの問題に対する答えではありません。このアルゴリズムは、フィボナッチ数列とほぼ同じように、キャッシュから最も恩恵を受けます。

CONST = 5いくつかのサンプル データ ( 、a = 0..10、 )を使用して、F# で短いテスト プログラムを作成した後b = 2..10:

  • 元のプログラムは 6.931 秒かかりました
  • キャッシュされたバージョンは 0.049 秒かかりました

解決策は、キーを持つディクショナリを保持し、tuple(a,b)計算する前に値を調べることです。キャッシュを使用したアルゴリズムは次のとおりです。

dictionary = new Dictionary<tuple(int, int), int>();

sub calc (a, b )
{
    if (dictionary.Contains(tuple(a,b)))
        return dictionary[tuple(a,b)];
    else
    {
        total = 0;
        if(b <= 1) 
            return 1
        if( 2*a > CONST)
            for i IN (1..CONST)
                total += calc(i, b-1);
        else
            for j IN (2*a..CONST)
                total += calc(j, b-1);

        dictionary[tuple(a,b)] = total;
        return total;
    }
}

CONST = 5編集：パフォーマンスの向上を引き起こしたのはテストの反復的な性質ではないことを確認するために、単一のパラメーターセット（ 、a = 6、 ）で両方をもう一度試しましたb = 20。

  • キャッシュされたバージョンは 0.034 秒かかりました
  • 元のバージョンはまだ実行中です... (2 分以上)
于 2013-04-12T15:48:08.223 に答える
0

反復アルゴリズムに変換できるのは末尾再帰アルゴリズムのみです。提供されたコードは、間違いなく末尾再帰ではないため、反復形式に簡単に変換することはできません。

パフォーマンスの問題の解決策はメモ化です

于 2013-04-13T01:16:00.197 に答える