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
.