꼬리 - 재귀 pow() 알고리즘을 memoization?

Question

난 꼬리 - 재귀 및 반복 계산 속도를 memoization 사용하는 pow() 계산하는 알고리즘을 찾고 있어요.

성능은 문제가되지 않습니다. 이것은 대부분 지적 훈련입니다. 기차 타기를 할 수있는 모든 구현이 다르기는했지만,이 두 가지 속성을 가진 것이 만족 스러웠습니다.

내 최고의 기회는 다음이었다

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) 

그것은 작동하지만, 모든 계산의 결과 memoize하지 않습니다 - 지수 1..exp/2 및 exp들만을.

Answer 1

캐시에 올바른 것을 기록하고 있다고 생각하지 않습니다. 다른 인수로 호출하면 매핑이 변경되었습니다.

(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,...)이지만 캐시에 이미 저장되어 있으므로 재귀가 중지됩니다.

함수는 acculumator 및 ctr으로 계산할 것으로 예상되는 것과 전혀 다른 캐싱을하기 때문에 매우 혼란 스럽습니다.

Answer 2

SICP section 1.2.4 Exponentiation에 설명 된 연속 제곱 기술을 사용하면 성능이 향상됩니다. 그것은 memoization을 사용하지 않지만, 일반적인 접근법은 O (n) 대신에 O (log n)이므로, 여전히 개선이 있어야합니다.

나는 운동 1.16 here에서 반복적 인 과정에 대한 해결책에 대해 이야기합니다.

Answer 3

이 너무 늦었 방법이지만, 거기에 아무도 대답을 찾고, 여기있다 :

int powMem(int base,int exp){ 
    //initializes once and for all 
    static map<int,int> memo; 

    //base case to stop the recursion 
    if(exp <= 1) return base; 

    //check if the value is already calculated before. If yes just return it. 
    if(memo.find(exp) != memo.end()) 
     return memo[exp]; 

    //else just find it and then store it in memo for further use. 
    int x = powMem(base,exp/2); 
    memo[exp] = x*x; 

    //return the answer 
    return memo[exp]; 
} 

이이 메모 배열 사용 -지도를 정확하게는 - 이미 계산 된 값을 저장합니다.