Soyez le premier à donner votre avis sur cette source.
Vue 31 235 fois - Téléchargée 381 fois
#iterative implementation #complexity O(n) def fibo_it(i): a,b,cpt=0,1,0 while cpt <= i: if cpt < 2 : c = cpt else : c=a+b a=b b=c cpt+=1 return c #iterative implementation of generator def fibogen_it(i): a,b,cpt=0,1,0 while cpt <= i: if cpt < 2 : c = cpt else : c=a+b a=b b=c cpt+=1 yield c #simple recursive implementation #complexity O(2^n) def fibo_rec(i): if i < 2 : return i return fibo_rec(i-1)+fibo_rec(i-2) #recursive implementation of generator def fibogen_rec(i): for j in range(i) : yield fibo_rec(j)
ocaml peut-etre interprete ou compile en bytecode ou en binaire classique.
Sérieux, tu as déjà vu une lib maths en interprété profond ?
pour des maths, on en a quoi a faire du C ou de l'asm ?
le C, ca peut se comprendre pour la vitesse, mais pour cette fonction, osef en fait, vu qu'on depasse la taille d'un int tres vite, une complexite O(n) et pas O(2^n) suffit, on est pas oblige de chercher le mili-cycle ni le O(1)... (il parait qu'une solution en O(1) existe)
mon code caml est recursif et compacte...let fibo n let rec a function | (f0, f1, 1) -> f1 | (f0, f1, n) -> a( f1, f1+f0, n-1 ) in a (1, 1, n);;
une ligne...
il est de complexite O(n), et est relativement rapide
en python, je ne saurais pas le recoder, desole
Avant tout, on optimise l'algo en C qui a l'avantage de s'écrire comme on respire. L'ASM coulera de source ensuite et sera d'ailleurs inutile sur un algo aussi simple, le compilo sortira direct un ASM optimal si on lui a bien expliqué en C ce qu'on veut.
Suffit pour Fibo de placer la valeur de sortie en 1er et on aura au maxi qu'1 seul saut de code vers la sortie unique vu que EAX deja mis.
DWORD __fastcall FibonacciC(DWORD Rank)
{
DWORD vret 0, n2 0;
if(Rank == 0) goto fiboEXIT;
vret = 1;
if(Rank <= 2) goto fiboEXIT;
n2 = 1;
if((Rank -3) 0) goto goRET;
if(Rank & 1) {
vret = 2;
if(--Rank == 0) goto goRET;
}
do {
n2 += vret;
vret += n2;
} while(Rank -= 2);
goRET: vret += n2;
fiboEXIT: return vret;
}
__declspec(naked) DWORD __fastcall FibonacciASM(DWORD Rank)
{ // ECX = Rank
__asm {
xor eax, eax
test ecx, ecx
je short fiboEXIT
mov eax, 1
cmp ecx, 2
jbe short fiboEXIT
sub ecx, 3
mov edx, eax
je short goRET
test cl, al
je short goDO
sub ecx, edx
lea eax, [edx+1]
je short goRET
goDO:
add edx, eax
add eax, edx
sub ecx, 2
jne short goDO
goRET:
add eax, edx
fiboEXIT:
ret 0
}
}
Bien sur la complexité d'un tel code est horrible !
Je vais éditer pour indiquer la complexité des méthodes, mais tu remarqueras que la fonction itérative est déjà en O(n).
En fait j'ai ajouter ce code car j'étais surpris qu'il ne soit pas sur Codes-Sources ! Il faut faire vivre python c'est tellement joli !
Vous n'êtes pas encore membre ?
inscrivez-vous, c'est gratuit et ça prend moins d'une minute !
Les membres obtiennent plus de réponses que les utilisateurs anonymes.
Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.
Le fait d'être membre vous permet d'avoir des options supplémentaires.