Salut,
la question est dans le titre et ma réponse est, après expérience : très mal !
Sans rire, je suis contraint même pour des trucs relativement basiques de passer en itératif : quelqu'un saurait-il m'expliquer pourquoi ?
Merci d'avance !
PS : Merci d'éviter le troll récursif vs itératif...
Re : Comment python gère-t-il la récursivité ?
Peut-être que dans l'appel d'une fonction, le compilateur remplace simplement l'appel de fonction par le code que contient la fonction. Comme dans un #define du C
Après, je ne connais pas du tout Python. Donc je peut me tromper entièrement.
Pole.
Oh non! C'est tout de même un language plus évolué que ça... (En plus il n'y a pas de compilateur...)Envoyé par Pole
Quels genre de codes te posent problèmes?
Personellement je n'ai jamais eu de problèmes avec ça.
En même temps j'essaye toujours de préférer à la récursivité des structures de piles que je gère moi même.
Salut,
Par exemple si je lui demande de parcourir une liste de facettes pour les afficher, il explose dès que la liste a plus de 1000 éléments.Quels genre de codes te posent problèmes?
La fonction est du genre :
Alors qu'en faisantCode:def dessineListe(list): if list=[]: print "ok" else: list[0].dessine() # la méthode dessine() est dans la classe "facettes" dessineList( list[1:len(list)] )
je n'ai pas de pb.Code:def dessineListe(list): for idx in range(len(list)): list[idx].dessine()
J'ai un autre exemple où il faut ramer pour "dérécursifier" (ça se dit ?). En l'état, c'est super long (à partir de n=25, il faut compter en minutes puis en heure...).
Désolé, c'est un peu (beaucoup) crade comme code, mais bon je le mets quand même : la méthode renvoie une liste constituée des partitions de n (les listes d'entiers dont la somme de ses éléments vaut n).
Par exemple :Code:def buildyoung(n): if (n==1): return [[1]] if (n<1): return [[]] idx=1 r=[[n]] while (idx<n): l=buildyoung(n-idx) for partition in l: if (idx<=partition[len(partition)-1]): partition[len(l):len(l)]=[idx] r[len(r):len(r)]=[partition] idx=idx+1 return r
Cordialement.Code:>>> buildyoung(6) [[6], [5, 1], [4, 1, 1], [3, 1, 1, 1], [2, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1], [2, 2, 1, 1], [3, 2, 1], [4, 2], [2, 2, 2], [3, 3]]
Tu envoie un tableau de 1000 puis 999,998,... cases!!!!
Si tu sommes ça donne environ 500 000! La pile doit craquer (Il me semble que la pile d'un programme est limitée à 1Mo donc il suffit que la taille d'une facette soit plus grande que 2 octets,....). A moins que Python envoies l'adresse de la première case du tableau comme en C. (Encore une fois, je ne connais pas Python)
Pole.
Je rapelle qu'un slice [x:y] recrée une nouvelle liste à chaque fois...
C'est ça qui pose problème, pas la récursivité.
Il faut t'arranger pour éviter de recopier le la mémoire inutilement... (ex: passer les indices en paramètres et la liste par référence)
Attention, encore une fois python est interprété, les arguments ne vont pas directement sur la pile et on n'y crée pas de tableaux non plus...
Ici ce qui se passe c'est qu'à chaque appel de R(slice(liste)) slice crée une copie d'une partie de liste sur un genre de heap, et passe le tout par référence à R.
Le problème c'est que malgrès un passage par référence, une copie est réalisée...
SAlut,
ok merci pour les précisions : ça venait donc de mon programme (ce à quoi il fallait bien s'attendre
Bonne soirée !
En fait c'est bien une liste (et remarquablement bien foutue d'ailleurs) mais dans son modèle il faut un constructeur de copies... C'est "[:]" qui est utilisé. (d'ailleurs à mon avis un slice qui modifierai en même temps l'original serait assez *********...)SAlut,
ok merci pour les précisions : ça venait donc de mon programme (ce à quoi il fallait bien s'attendre
Bonne soirée !
Salut,
ok merci, mais dans ce cas il n'existe pas une fonction qui renvoie la queue d'une liste ?
Bonne journée.
Par défaut je ne crois pas...
Par contre tu peux faire un classe de "wrapper" qui transforme __getitem__(i) en __getitem__(i+k) sur la liste originale. Ensuite tu surcharges getslice pour renvoyer l'instance de wrapper à la place d'une copie de la liste, et le tour est joué.
Salut,Tiens, en passant, on peut surcharger des méthodes ? Car j'avais lu que c'était impossible (et mes tentatives ont été courtoisement rejetées...)
Ça dépend de ce que tu apelles surcharger.
Faire de la surcharge d'opérateur, oui; surcharger au sens faire la différence entre toto(a) et toto(a,b) comme des méthodes indépendantes, non.
Ceci dit un on peut parfaitement faire une méthode toto avec liste de paramètres variable et appel de la méthode ad hoc après quelques tests (attention à ne pas perdre la généricité lors de ces tests).
Bonsoir,
Je ne connais pas trop python, mais je me permets une remarque d'ordre général. À la limite du troll, pas trop j'espère.
Quand on a une culture C++ (comme moi), il n'y a pas de différence entre une surcharge du genre:int f(int a) ;ou une du genre:
int f(int a, int b) ;int operator + (int a) ;Juste une question de notations.
int operator + (int a, int b) ;
Maintenant, pourquoi C++ ne fait-il pas la différence entre:int f(int a) ;ce qui permettrait des choses du style:
double f(int a) ;int i = f(0) ;Techniquement, ce serait faisable. Mais, mis à part les problèmes de lisibilité, ça supposerait de connaître tous les constructeurs par défaut d'une classe, y compris ceux générés automatiquement par le compilo... pénible. Mais dommage quand même, non?
double x = f(0) ;
-- françois
Le plus gros problème dans ce cas serait de différentier l'appel de deux méthodes...
Ex:
Code:int toto(int a); void toto(int a); int main() { toto(a); // j'appelle qui moi? au secours!!! }
Les slicing marche aussi avec les indices négatifs et nulls.
Code:>>> a [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] >>> a[-1] 9 >>> a[-2:] [8, 9]
Certes, mais je crois qu'il voulait plus une référence vers une fin de liste compte tenu des problèmes qu'il recontre...
EDIT: bienvenue, au fait!
Merci et bonjour a tous !
Pour réponde à la question de départ, le problème se situe dans l'algorithme.
La quasi-totalité des appels à buildyoung() sont effectués inutilement.
En stockant simplement les résultats temporaires on passe d'une complexité o(n!) à o(n log n) :
Sur mon PC, pour n=25, je passe de 114 sec à 0,03 sec. Vous avez dit efficace ?Code:def buildyoung(n, tempData={0:[[]]}): if n not in tempData: r=[[n]] for idx in range(1,n): for partition in buildyoung(n-idx, tempData): if (idx<=partition[-1]): r.append(partition+[idx]) tempData[n] = r return tempData[n]
Salut,
ah ben oui, c'est logique !
Merci.
Re : Comment python gère-t-il la récursivité ?
Bonsoir,
je voudrais revenir à la question de départ (s'il y a encore du monde).
Je suis un fan de la récursivité et surtout de la récursivité terminale et je suis perplexe quant à la manière dont python gère la récursivité, terminale ou pas d'ailleurs.
Exemple: Fibonacci:
# Fibonacci itératif
def fibo1(n):
f0=0; f1=1
if (n==0): return 0
if (n==1): return 1
f2=1
i=1
while (i<n):
f2,f1,f0 =f1+f0, f2, f1
f1,f0 =f2, f1
i=i+1
return f2
# Fibo récursif terminal
def fibo2(n,acc1,acc2):
if (n==0): return acc2
if (n==1): return acc1
return fibo2(n-1,acc1+acc2,acc1)
# Fibonacci DPR
def fiboDPR(n):
if (n==0): return 0
if (n==1): return 1
if (n==2): return 1
(p,r)=divmod(n,2)
if (r==0):
return fiboDPR(p)*(fiboDPR(p-1)+fiboDPR(p+1))
if (r==1):
fp=fiboDPR(p)
fp1=fiboDPR(p+1)
return fp*fp + fp1*fp1
Pour n=10000 on a les temps
Fibo it 0.0310001373291
Fibo RT 0.140999794006
Fibo DPR 0.219000101089
on voit que fibo2 est plus lent, ce qui me surprend (mais c'est effectivement peut être à caase du passage de paramètres ?) mais que fiboDPR soit le plus lent des trois, là je ne comprends pas du tout.
Avec le module timeit: (n=100, pour n=1000 j'ai des débordements de récursivité...)
Temps de fiboDPR:0.00069855928421
Temps de fibo1:6.69407844543e-05
Temps de fibo2:0.000101609230042
Je ne vois pas le problème... fibo1 est itératif, et va à l'essentiel, dans fibo2 on fait les mêmes calculs plus les appels, et dans fiboDPR on se tape encore plus d'appels de fonctions...
ben non justement,
dans fiboDPR comme tu divise "en gros" n par 2, tu ne calcules pas tout les nombres entre f0 et f(n), loin de là et même si tu fait un peu plus d'appels à cause des appels pour fiboDPR(0) et fiboDPR(1).
Dans certains environnements comme Mathematica ou Maple ("langages" interprétés tous les deux) ça va généralement plus vite que le récursitivité, idem pour fibo2, j'ai fait plein de tests.
ça veut dire que l'appel d'une fonction en python est "cher" ?
ps: il faut ajouter par exemple
import os, sys, time
sys.setrecursionlimit(100000)
pour aller au delà de la limite
houps,
je voulais dire "ça va généralement plus vite que la version itérative"
Si tu veux aller plus vite, passe à des langages compilés (C,C++,Pascal....).
Et si tu veux accélérer fiboDPR,tu peux faire que 2 appels si r=0 : si tu connais Fn et Fn-1 tu devrais facilement connaître Fn+1
Essaye de passer en itératif(il faut calculer en même temps Fn et Fn-1), peut être que Python enregistre les appels des fonctions (tu peux tester en utilisant la définition de la suite Fn=Fn-1+Fn-2 et F1=1,F2=1,pour calculer comme ça,il faut 2^n appels,si Python les mémorise,ça passe à n).
Pole.
Merci pour le truc, je connaissais pas.
J'ai fait le test en C pour fibo1 et fibo2, fibo2 est plus lent, mais pas tellement, ce qui me fait dire que oui, les appels de fonction en python sont chers...
Dailleurs c'est pas compliqué, fibo2 fait exactement la même chose que fibo1, avec un appel en plus à chaque addition, ce qui suppose recopier plein de fois dans la mémoire les résultats (au moins en C)...
Re : Comment python gère-t-il la récursivité ?
http://forums.futura-sciences.com/im...ies/Bravo1.gif
AH, j'ai honte,
un appel pour "rien" dans fiboDPR
avec
# Fibonacci DPR
def fiboDPR(n):
if (n==0): return 0
if (n==1): return 1
if (n==2): return 1
(p,r)=divmod(n,2)
if (r==0): fp=fiboDPR(p); fpm1=fiboDPR(p-1); fp1=fp+fpm1; return fp*(fpm1+fp1)
if (r==1): fp=fiboDPR(p);fp1=fiboDPR(p+1) ; return fp*fp + fp1*fp1
on a:
pour n=10000
Fibo it 0.0159997940063
Fibo RT 0.125
Fibo DPR 0.0150001049042
pour n=11000
Fibo it 0.0309998989105
Fibo RT 0.109999895096
Fibo DPR 0.0150001049042
là ça me rassure!
Merci.
