Bonsoir a tous,

j'ai écris une fonction en utilisant la récursivité qui permet de savoir si oui ou non, on peux arriver un a un Total avec n billet seulement, en utilisant un tuple de différent billet, par exemple:

>>>atc_rec(7=n,(7,10),70=total)

True

J'ai donc écris cela 

def atm_rec(total, values, n):
    if total == 0 and n == 0:
        return True

    if total < 0 or n < 0:
        return False

    for v in values:
        if atm_rec(total - v, values, n - 1):
            return True

Puis dans une autre question on me demande d'utiliser la memoization pour que le code soit plus rapide, j'ai écris cela :

def atm_mem(total, values, n,memo=None):
        if memo==None:
                memo=[]
        if (total,n)in memo:
                return False
        else:
                memo.append((total,n))
        if total == 0 and n == 0:
                return True
        if total < 0 or n < 0:
                return False
        for v in values:
            
                if atm_mem(total - v, values, n - 1,memo):
                        return True
        return False
        

Mais a l'aide de timeit je me rend compte qu'il est près de 4 fois plus lent !! Je comprends pas pourquoi...

-
Edité par Ilan00 20 décembre 2016 à 17:39:05

Bonjour,

ta fonction atm_rec est mal fichue, il manque un bout je suppose …

Ensuite la mémoisation n'est effective que dans le cas où tu t'évites des calculs redondants et s'il y en a pas mal. Par exemple dans ton dernier fil sur la pyramide avec la version dp tu n'aurais rien gagné. S'il y en a peu ou pas tu ne gagneras rien ; ce n'est pas une technique qui te garantit une accélération.

Il y a aussi deux niveau de mémoisation, le premier qui se fait «à l'intérieur de la fonction» lors de la récursion et qui est perdu entre deux appels de niveau 0 et le second qui se fait tout au long de la durée de vie du programme.

effectivement dans le premier code il manque return False a la fin, il a pas été copie .. 

Alors faut que je change mes codes pour que je puisse par la suite utiliser la memoization pour répondre a l’énoncé de mon DM ... 

Bon déjà mémoiser une fonction c'est cacher (dans le sens mettre en cache) les résultats, tous les résultats et pas uniquement une partie. Cela signifie que tu devrais utiliserun dictionnaire qui contiendrait en clé les paramètres et en valeur le résultat de la fonction avec ces paramètres. C'est tout aussi utile de savoir que ta fonction renvoie true pour (a,b) que de savoir qu'elle renvoie false pour (c,d) …

En testant, je trouve une accélération de l'ordre de 2.5 :

In [1]: %timeit atm_rec(70, (7,10), 7)
10000 loops, best of 3: 189 µs per loop

In [2]: %timeit memo=dict();atm_mem(70, (7,10), 7, memo)
10000 loops, best of 3: 75 µs per loop

J'ai pris une version légèrement modifiée de atm_rec :

def atm_rec(total, values, n):
  if n==0 or total<0:
    return total==0
  else:
    for v in values:
      if atm_rec(total-v, values, n-1):
        return True
    return False

Ma version mémoisée l'a été avec un dictionnaire.

J'ai pas comprius cette partie du code :

def atm_mem(total, values, n,memo=None):
        if memo==None:
                memo={}
        memo_key=(total,n)
        if total == 0 and n == 0:
                return True
        if total < 0 or n < 0:
                return False
        for v in values:
            if memo_key not in memo:
                atm_mem(total - v, values, n - 1,memo)
                return True
        return False

 print timeit.timeit("atm_rec(7100,(20,10,15,21,47),2)", 'from __main__ import *', number=50000)

Warning (from warnings module):
  File "<timeit-src>", line 2
SyntaxWarning: import * only allowed at module level
0.302622864715

print timeit.timeit("atm_mem(7100,(20,10,15,21,47),2)", 'from __main__ import *', number=50000)

Warning (from warnings module):
  File "<timeit-src>", line 2
SyntaxWarning: import * only allowed at module level
0.108204262872

Ca a l'air de marche ...

Ca marche pas, juste ca renvoi True....:((((

-
Edité par Ilan00 20 décembre 2016 à 21:52:18

heu … tu les mets quand les résultats dans ton dico ???

Tu as bien des exemples dans ton cours, non ?

Par exemple avec fibonacci →

def fibo_rec(n):
  if n<2:
    return 1
  else:
    return fibo_rec(n-1) + fibo_rec(n-2)

def fibo_mem(n, memo=None):
  if memo is None:
    memo={0:1, 1:1}
  if n in memo:
    return memo[n]
  else:
    result=fibo_mem(n-2)+fibo_mem(n-1)
    memo[n]=result
    return result

def atm_mem(total, values, n,memo=None):
        if memo==None:
                memo={}
        memo_key=(total,n)
        if n==0 or total<0:
            return total==0
        if memo_key not in memo:
                for v in values:
                        if atm_mem(total - v, values, n - 1,memo):
                            memo[memo_key]=True
                            return memo[memo_key]
                memo[memo_key]=False
                return False

#Il reste toujours + lent ...        

-
Edité par Ilan00 21 décembre 2016 à 17:56:45

La mémoisation c'est vraiment tout con :

au lieu d'appeler une fonction avec ses paramètres pour obtenir un résultat, on cherche dans le dico avec les mêmes paramètres si le résultat a déjà été calculé …

La clé est donc évidemment «les paramètres» et la valeur associée est «le résultat». Donc dès que tu dois calculer un résultat car il n'est pas dans le dico, une fois calculé, et ce quelle que soit sa valeur, tu le rajoute au dico.

Ton cours doit t'expliquer ça non ?

c'est ce que j'ai fais et ca marche dans cette exos..

le tout est de bien identifier la/les clefs et le resultat

par contre dans l'exos des pyramide, notre clef c'est la pyramide, mais la pyramide est une liste et donc mutable alors que le clefs doit etre  immutable.

tout comme le resultats upper[0][i] ...  du coup je suis bloque 

Parce que dans le cas de la pyramide tu n'essayes pas de résoudre plusieurs fois le même problème … la version programmation dynamique fait que la mémoisation n'apporte rien ; il me semble l'avoir expliqué dans l'autre sujet.

Si tu veux t'en assurer, transforme ta liste de liste en simple chaine de caractères … tu pourras t'en servir comme clé ; mais à nouveau : cela ne servira à rien, enfin ça ne servira pas plus que de pisser dans l'océan.

Exact ... donc faut que je change mon code initial et j'applique la methode diviser pour regner pour en suite appliquer la memoization

tu as la solution du code de la pyramide en appliquant diviser pour régner ?

-
Edité par Ilan00 21 décembre 2016 à 21:47:27

hum … tu veux donc une solution moins performante pour pouvoir en améliorer les perfs qui seront moins bonne que la solution actuelle ? c'est pas un peu ridicule ?

Oui l'autre solution (celle qui serait améliorable par mémoisation) je te l'ai déjà expliquée dans l'autre fil … Il faut aussi apprendre à comprendre ce que je te dis.

Effectivement on ne se comprends pas ... Tu me dis "la version programmation dynamique fait que la mémoisation n'apporte rien" 

Je dois écrire une fonction sans memoization puis une autre avec dans le but d’améliorer le code.

La version dynamique c'est bien le code que j'ai ecris :

def max_trail( pyramid ):
  if len(pyramid) == 1:
    return pyramid[0][0]
  else:
      for i in range(len(pyramid[1])):
          pyramid[1][i]=max(pyramid[0][i]+pyramid[1][i], pyramid[0][i+1]+pyramid[1][i])
      upper=pyramid[1:]
  return max_trail(upper)
max_trail([[8,6,3,1],[3,4,2],[5,7],[4]])

Celle ci ne peux pas être améliorer par memoization, n'est  ce pas ?

non.

Pourquoi ?

Simplement parce qu'à chaque appel récursif (il n'y en a qu'un) les paramètres donnés sont plus petits que ceux que tu as déjà calculés … donc tu ne peux pas les avoirdéjà calculés … donc il ne peuvent pas être dans le dico … donc la mémoisation n'apporte rien … ça fait plusieurs fois que je te le dis.

Nous sommes donc d'accord, j'avais donc mal compris ce que tu avais dis précédemment ...

dans le topic precedent tu as ecris :

def memoize(f):
  memo = {}
  def memoized(x):
    if x not in memo:           
      memo[x] = f(x)
    return memo[x]
  return memoized
 
@memoize
def max_trail( pyramid ):
  ...

Je n'ai pas compris .. tu memoize quoi ? 

Soit tu mémoises «un appel» : ton mémo ne sera rempli que lors d'un appel. Si tu as deux pyramides P1 et P2 Si P1 et P2 sont identiques alors il y aura le même nombre d'appel, y compris avec ton mémo.

Le lru_cache sert à mémoiser sur plusieurs appels → l'appel avec P1 amènera à faire des calculs, si tu rappelles avec P2 identique à P1 plus aucun calcul ne sera fait.

Je t'en avais déjà parlé aussi.

C'est au Père Noël qu'il faut demander des cadeaux … pas à Picodev …

D'autant plus que Saint Nicolas est passé avant … si tu lisais bien mes messages :

PicoDev a écrit:

Alors si on rentre un peu dans les détails, ce que tu as fait s'appelle de la programmation dynamique. Cela ressemble à la technique «diviser pour régner». Dans les deux cas on résout un problème en résolvant des problèmes plus petits et a priori plus simples. La différence essentielle est que dans le cas «diviser pour régner» les sous-problèmes doivent être indépendants, ne pas se recouvrir alors que dans le cas programmation dynamique c'est justement une propriété qu'on recherche.

Une version diviser pour régner de ton problème consisterait en

// ici on considère qu'on a comme paramètre la pyramide
// listée à partir du sommet
// par exemple : [ [4], [5,7], [3,4,2], [8,6,3,1] ]
fonction max_trail(pyramid)
  si longueur(pyramide) = 1 alors
    renvoyer valeur du sommet
  sinon
    sous_pyramide_gauche = gauche(pyramide)
    sous_pyramide_droite = droite(pyramide)
    renvoyer max(
         sommet(pyramide)+max_trail(sous_pyramide_gauche),
         sommet(pyramide)+max_trail(sous_pyramide_droite)
                )

Le problème dans la version diviser pour régner est qu'on effectue plusieurs fois le calcul sur la sous pyramide [ [6,3], [4] ]. Alors un moyen est effectivement de mémoiser les résultats, on pourrait utiliser un dictionnaire → si la pyramide est une clé du dico alors tu as déjà calculé le résultat et tu peux directement le renvoyer, sinon tu calcules le résultat et tu ajoutes ça dans le dico. En gros :

fonction max_trail(pyramid)
  si pyramid dans dico alors
    renvoyer dico[pyramid]
  sinon si longueur(pyramide) = 1 alors
    resultat = valeur du sommet
  sinon
    ...
    resultat = max( ... )
  dico[pyramid] = resultat
  renvoyer resultat

Tu vois que la version diviser pour régner semble plus complexe et nécessite une mémoisation pour éviter plsuieurs calculs identiques alors que la version programmation dynamique est plus simple et ne nécessite aucun mémoisation car aucun calcul n'est dupliqué.

Edit: petite clarification, oui on pourrait utiliser la mémoisation y compris dans le cas programmation dynamique mais pas sur la fonction elle-même mais sur la partie «calcul». Par exemple tu pourrais mémoiser la fonction max pour améliorer ses perfs, mais tu ne mémoiserais plus la fonction elle-même comme dans le cas diviser pour régner.

-
Edité par PicoDev 19 décembre 2016 à 18:11:45

Après faut évidemment se creuser un poil la tête …

J'ai une erreur de type : IndexError: list index out of range

def max_tra(pyramid,row=0,col=0):
    sous_pyramid_gauche=[]
    sous_pyramid_droite=[]
    if len(pyramid) ==1:
        return pyramid[0][0]
    else:
        for left in pyramid[1:]:
            l=len(left)/2
            sous_pyramid_gauche.append(left[0:l])
            l=0
        for right in pyramid[1:]:
            l=len(right)/2
            sous_pyramid_droite.append(right[l:])
            l=0
        last,lower=pyramid[0], pyramid[1:]
        for i in range (len(lower[0])):
            lower=max(pyramid[0][0]+max_tra(sous_pyramid_gauche),pyramid[0][0]+max_tra(sous_pyramid_doite))

-
Edité par Ilan00 22 décembre 2016 à 8:48:36