Algorithme pow() récursif en queue avec mémo?

Question

Je suis à la recherche d'un algorithme pour calculer pow() qui est récursif et utilise la mémoisation pour accélérer les calculs répétés.

La performance n'est pas un problème; C'est surtout un exercice intellectuel - j'ai passé un train à venir avec toutes les différentes implémentations pow() que je pouvais, mais je n'ai pas réussi à en trouver un qui me plaisait avec ces deux propriétés.

Mon meilleur coup est la suivante:

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) 

Il fonctionne, mais il ne memoize pas les résultats de tous les calculs - que ceux avec des exposants 1..exp/2 et exp.

Answer 1

Je ne pense pas que vous enregistrez la bonne chose dans votre cache, le mappage a changé lorsque vous l'appelez avec des arguments différents.

Je pense que vous devez avoir un cache de (base, exp) -> pow (base, exp).

Je comprends ce que ctr est pour, et pourquoi seulement la moitié de ce que vous attendez est enregistré.

Considérons calc_tailrec_mem(2,4): Premier niveau, pow (2,1) est enregistré comme 2, le niveau suivant = calc_tailrec_mem(2,3,...), et pow (2,2) est enregistré. Le niveau suivant est calc_tailrec_mem(2,2,...), mais cela est déjà enregistré dans le cache, donc la récursivité s'arrête.

La fonction est très déroutante car elle met en cache quelque chose de complètement différent de ce qu'elle est censée calculer, en raison de l'acculumator et ctr.

Answer 2

Vous obtiendrez de meilleures performances si vous utilisez la technique d'équerrage successif décrite dans SICP section 1.2.4 Exponentiation. Il n'utilise pas de mémo, mais l'approche générale est O (log n) au lieu de O (n), vous devriez donc encore voir une amélioration. Je parle de la solution au processus itératif de l'exercice 1.16 here.

Answer 3

C'est trop tard, mais tout le monde là-bas à la recherche de la réponse, la voici:

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]; 
} 

Il utilise le tableau mémo - une carte, pour être exact - pour stocker les valeurs déjà calculées.