les arbres binaires - Page 3

non mais ct juste pour faire remarquer l'ironie de l'archi x86 actuelle, les coeur sont risc, mais l'instruction set est cisc, bref

En effet.
Personnellement, je préfère disposer des instructions qui permettent de faire une opération simple et courante (addq.w #1,mémoire en 68k) sans avoir à faire un paquet d'instructions à la place (ldr rn,addr; ldr rn2,[rn]; add rn2,rn2,#1; str rn2,[rn] en ARM, si je ne me trompe pas). Pas de moveq et d'addq/subq en x86 (xor eax,eax, (inc/dec)* eax; (inc/dec)+ eax)...

En pratique, un RISC bien fait (l'ARM en l'occurrence) marche très bien pour les petites plateformes (c'est ce qu'ont la plupart des PDAs, et la HP-49G+, sans oublier les GameBoy Advance au moins). A noter que le reste utilise souvent le 68000 - modèles plus anciens de Palm, TI-68k), mais sur de grosses plateformes, c'est beaucoup moins évident.
Même si je sais que le SPARC (que je connais relativement mal) n'est pas aussi bien fait que l'ARM, au boulot de mon père, ils sont en train de passer des Sun qui coûtent assez cher à des PC portables récents Linux qui font le boulot trois fois plus rapidement (et encore, la comparaison est faite sur une machine Sun plus puissante que celles qu'ils ont sur leurs bureaux)... Encore mieux, la licence du soft coûte moins cher pour Linux que pour Unix...

hum le sparc suxxx...

opur faire un jmp propre il faut une instruction qui la suit (oui oui c'est a cause des pipelines)

genre

(c'est du pseudo asm, je me rapelle plus des mnemoniques des sparcs)

jmp nextinstruction
add r1,r2

gen add r1,r2 est executé avant le jmp :/

Sinon ce qui est sympa avec les sparcs c'est la methode de gestion des registres (globalement on en a une infinité)
Perso la meilleur archi RISC pour des gros systemes reste le Power4 Power5 et sa déclisont grand publique, le PowerPC

C'est d'ailleurs un PowerPC 64 bits qui est dans le Cell...

un G5 ? ou un Power5 ?

Plus on peut se passer du recursif, mieux c'est.

Euh c'est derive du POWER5, mais c'est un core pas mal simplifié et donc bcp moins efficace qu'un G5... En contrepartie ca lui permet de prendre pas beaucoup de place (donc plus de place pour les coprocesseurs) et de tourner a des frequences de l'ordre de 4 GHz

JS> trop gros, passera pas

C'est pas trop gros... c'est ce qu'on t'apprend en cours d'algo...

sw33t... donc l'ideal en fait ce serait d'avoir une seule grosse fonction iterative avec une grosse boucle et une pile qui remplace les appels de fonctions, pour eviter le recursif a tout prix ?

cela dit j'ai p-e pas eu des cours d'algo aussi bons que les tiens, donc faudra que tu detailles un peu plus ton propos si tu veux etre pris au serieux ^^

[HS=Troll]

Pollux :
sw33t... donc l'ideal en fait ce serait d'avoir une seule grosse fonction iterative avec une grosse boucle et une pile qui remplace les appels de fonctions, pour eviter le recursif a tout prix ?

cela dit j'ai p-e pas eu des cours d'algo aussi bons que les tiens, donc faudra que tu detailles un peu plus ton propos si tu veux etre pris au serieux ^^

C'est comme les GUI il faut absolument les ecrire en non objet et meme si possible directemetn en ASM
[/HS]

Godzil :
[HS=Troll]

Pollux :
sw33t... donc l'ideal en fait ce serait d'avoir une seule grosse fonction iterative avec une grosse boucle et une pile qui remplace les appels de fonctions, pour eviter le recursif a tout prix ?

cela dit j'ai p-e pas eu des cours d'algo aussi bons que les tiens, donc faudra que tu detailles un peu plus ton propos si tu veux etre pris au serieux ^^

C'est comme les GUI il faut absolument les ecrire en non objet et meme si possible directemetn en ASM
[/HS]

C'est vrai, c'est tellement plus convivial à programmer et à entretenir en plus

J'ai pas dit absolument il y a un juste milieu. Mais pour certains le parcourt d'arbre se voit qu'en recursif...

Bah c'est souvent plus adapté, apres ca depend...

Je suis du meme avis que JackosKing :
le récursif plus on peut s'en passer mieux c'est.
l'itératif est [u]GENERALEMENT[u/] + rapide et prends moins de place mémoire.
Mais ce qui fait la force de l'itératif c'est qu'il est bocoup bocoup + stable
Ex le tri bulle est sans conteste + lent que le tri fusion
Seulement si on essaye de traiter de grande liste et bien l'algo recursif a de tres grande chance de planter a causer d'un débordement de la méméoire.
Dans la pratique on évite d'écrire en récursif a cause des fameux "buffer overflow" qui représente de grosse faille sécurité
Seulement il est indéniable que certain problemes sont bien mieux résolu en récursif.

Super remontage, super interessant

comparer tri a bulle et tri fusion si encore ct le meme algo c'est n'importe quoi

et je vois pas en quoi l'algo recursif aurait plus tendance a foirer sur de tres grands ensemble qu'un algo itératif, si ton ensemble de donnée tiens en mémoire, l'algo ne foirera pas, et le recursif n'a jamais été un des facteurs de risque opur les buffer overflow

désolé je me suis mal exprimer et meme completement gourer à minuit on fatigue.
En fait ce que je voulais dire c le fait d'empiler a chaque fois les variables du programme ca prends enormement de place.
Genre pour les algo de tri
si augmente la taille de la liste tres vite la machine ne pourra plus executer l'algo recursif parce que trop gourmand en memoire.
tandis qu'en utilisant 2 for imbriqués comme pour le tri par insertion ce sera certe + long mais surtout ca ne planteras pas puisque le programme ne s'executera qu'une fois et que les seuls variables locales sont i,j, intermédaire

C'est encore + vrai pour le pascal ou on n'arrivait meme pas a calculer fibonnaci(50) en recursif
Meme probleme pour mon démineur en basic à partir du certaine profondeur "mem error"
du coup g du minorer le nombre de mines par 7 pour etre sur que le prog ne plante pas

voila ca reste un avis
mais presk n'importe kel prog en recursif peut planter
hanoi(30) sur ma caltos, fibo(50)....
alors qu'en les derecusifiant il tourne!

en relisant mon post je le trouve un peu bocoup manicheen
alors juste une precision j'adore le recursif surtout pour résoudre des enigmes des problemes complexes où souvent on a besoin d'arbre (de recherche ...) etc ou la il faut l'avouer ce serait hardu de le faire en itératif
Enfin bref le recursif a aussi bocoup de bon surtout pour résoudre des probleme théorique il fournit souvent des solutions courtes et intuitives (enfin pour moi) mais reste tout de meme dans la pratique un peu lent et pis surtout gourmand en memoire (je parle surtout en pascal)
A ce propos je sais pas pourquoi ils l'ont appelé turbo pascal parce kil est plutot lent ^^
le c est largement + rapide

Si tu rajoutes un peu d'évaluation paresseuse, t'as plus aucun problème pour ton fibonnacci(50), hein.

C'est moi ou #73, #76 & #77 sont limite illisible ?

Ben, quand un algorithme d'une sorte est polynômial en l'argument, et l'autre est exponentiel en l'argument, il est plutôt stupide d'utiliser l'algorithme exponentiel... C'est le but principal de la programmation dynamique: ne pas refaire les calculs déjà faits - ce qui est particulièrement trivial pour Fibonacci.

trop trop fort