Dijkstra, encore lui ;-)

Bonjour à tous,

Je vient d'implémenter l'algo de Dijkstra sous deux formes, avec un tableau, et avec un tas "normal" pas Fibonnaci... et à ma grande surprise ( ai-je tort ?) la version avec tableau est plus rapide que la version avec tas, pourtant la complexité en théorie est meilleur avec un tas !!! Qu'en pensez-vous ?

Quand on fait un TP et qu'on est sensé faire tourner la deuxième forme plus vite que l'autre, on se pose des questions existentielles à vous rendre malade...( ex : Dois-je poursuivre mes études ? )....

Augmente la taille et tu verras que le tas va passer progressivement devant. C'est une complexité en O(N²) par exemple pour l'un, mais cela peut être une vrai complexité égale à N²+ 2000N quand l'autre, c'est 1000Nlog(N) + N, donc le premier peut être plus rapide que le second sans aucun problème.

L'implémentation que tu as choisi pour un tas peut aussi jouer.

Par exemple, si pour chaque cellule tu réalises des allocations (par exemple malloc en C), ça peut être couteux en temps. Mais normalement, avec des grandes valeurs, cet algorithme devrait prendre le pas sur la version tableau.

Citation:

---

Envoyé par Miles

Augmente la taille et tu verras que le tas va passer progressivement devant. C'est une complexité en O(N²) par exemple pour l'un, mais cela peut être une vrai complexité égale à N²+ 2000N quand l'autre, c'est 1000Nlog(N) + N, donc le premier peut être plus rapide que le second sans aucun problème.

---

Montrer ce fait -- qu'il y a des zones ou un algo de complexite plus grande peut etre plus rapide -- est peut-etre d'ailleurs un objectif de l'exercice. Ce qui peut etre amplifie par un probleme d'implementation comme le signale Millie.

j'ai utiliser un tas de Fibonacci de la librairie "JGraphT"...
Et même avec ça, le tas est plus lent...sur des graphes de plus de 2000 sommets, et plus rapide sur des graphes de - de 1000 sommets ... 8O
J'y comprends plus rien, pourtant j'ai repris le même code du premier algo en tableau et j'ai juste changer la partie selection du prochain sommet ( le plus petit au sens de la distance ).

J'ai même essayer une implémentation perso du Tas directement dans l'algo, histoire d'éviter les appels entre objets fréquents...et là c'est à peine si les deux sont égaux en temps d'execution...m'enfin ce sont les mystères de l'algorithmique qui font son charme :mouarf:

Heu, une petite question qui peut paraître idiote : tu n'effectues pas un tri par tas à chaque itération, tu mets seulement à jour les positions des éléments dont tu modifies les distances dans la boucle la plus imbriquée ?

Citation:

---

Envoyé par borisd

Heu, une petite question qui peut paraître idiote : tu n'effectues pas un tri par tas à chaque itération, tu mets seulement à jour les positions des éléments dont tu modifies les distances dans la boucle la plus imbriquée ?

---

non, pas de tri mais la méthode insérer du tas modifie elle même les positions des elements insérés afin de garder une structure de tas, forcément. Et ça c'est sensé prendre un temps en O(log n).

Au départ le tas est vide, j'y insére le sommet de départ de l'algo, ensuite à chaque itération j'insére les succésseurs du sommet racine du tas en maintenant la structure du tas intacte.

le pire est que quand j'intègre la gestion du tas dans la classe de l'algo, cela n'améliore pas assez la vélocité.

ça y est, j'ai trouver d'où provenait mon problème ...
Je rajouter un sommet au tas même si le sommet y était déja...
donc il refaisait des calculs déja fait, pour rien ;)

Ce qui me semble bizarre c'est que ça marchait...

maintenant, le dijkstra en tas est plus rapide que le même avec un tableau...mais pas de beaucoup :aie: