2

pow()末尾再帰的であり、メモ化を使用して繰り返し計算を高速化する計算アルゴリズムを探しています。

パフォーマンスは問題ではありません。これは主に知的な演習です。電車に乗って、可能な限りさまざまなpow()実装を考え出しましたが、これら 2 つの特性を備えた満足のいく実装を思い付くことができませんでした。

私のベストショットは次のとおりでした。

def calc_tailrec_mem(base, exp, cache_line={}, acc=1, ctr=0):
    if exp == 0:
        return 1
    elif exp == 1:
        return acc * base
    elif exp in cache_line:
        val = acc * cache_line[exp]
        cache_line[exp + ctr] = val
        return val
    else:
        cache_line[ctr] = acc        
    return calc_tailrec_mem(base, exp-1, cache_line, acc * base, ctr + 1)

動作しますが、すべての計算結果を記憶するわけではありません - 指数1..exp/2とexp.

4

3 に答える 3

2

SICPセクション1.2.4べき乗で説明されている連続二乗手法を使用すると、パフォーマンスが向上します。メモ化は使用しませんが、一般的なアプローチはO（n）ではなくO（log n）であるため、改善が見られるはずです。

ここでは、演習1.16からの反復プロセスの解決策について説明します。

于 2010-04-04T17:45:40.730 に答える
0

キャッシュに正しいものを記録しているとは思いません。異なる引数で呼び出すと、マッピングが変更されました。

(base,exp) -> pow(base,exp) のキャッシュが必要だと思います。

何ctrの目的で、なぜあなたが期待するものの半分しか記録されないのかを理解しています。

考察calc_tailrec_mem(2,4): 最初のレベル、 pow(2,1) は 2 として記録され、次のレベル = calc_tailrec_mem(2,3,...)、および pow(2,2) が記録されます。次のレベルは ですがcalc_tailrec_mem(2,2,...)、それは既にキャッシュに保存されているため、再帰は停止します。

この関数は、アキュムレータと により、計算するはずのものとはまったく異なるものをキャッシュしているため、非常に混乱していctrます。

于 2010-04-04T17:59:44.927 に答える