+- JeuWeb - Crée ton jeu par navigateur (https://jeuweb.org)
+-- Forum : Discussions, Aide, Ressources... (https://jeuweb.org/forumdisplay.php?fid=38)
+--- Forum : Programmation, infrastructure (https://jeuweb.org/forumdisplay.php?fid=51)
+--- Sujet : Le meillieur algo de tri pour des nombres? (/showthread.php?tid=4794)
Le meillieur algo de tri pour des nombres? - Argorate - 06-05-2010
Hello,
Je suis entrain de me poser une question un peu bébette, mais je voulais savoir quel est selon vous l'algo le plus performant en php pour le tri de nombre relativement peu élevé?
Merci.
RE: Le meillieur algo de tri pour des nombres? - Allwise - 06-05-2010
Pas selon mais selon Wikipedia :
http://fr.wikipedia.org/wiki/Algorithme_de_tri#Comparaison_des_algorithmes_de_tris_en_place
RE: Le meillieur algo de tri pour des nombres? - Argorate - 06-05-2010
J'aurais préféré un avis parce que tu as déjà était dans un cas similaire^^
Surtout que je suis dans un cas très simple < 5 éléments.
Donc c'est sans doute pas la peine de déployer un quickshort juste pour ça non?
RE: Le meillieur algo de tri pour des nombres? - Sephi-Chan - 06-05-2010
Pourquoi ne pas utiliser la fonction native de PHP, sort() ?
Sephi-Chan
RE: Le meillieur algo de tri pour des nombres? - Argorate - 06-05-2010
Moi je vois rien contre, mais justement une partie de la question c'est es-ce qu'il y a mieux?
D'autant plus qu'il n'est pas donnée la Complexité asymptotique au pire des cas. C'est dur de comparé au niveau performance quand on ne donne pas la complexité
Curiosité: C'est basé sur quel algo cette fonction?
RE: Le meillieur algo de tri pour des nombres? - Sephi-Chan - 06-05-2010
(06-05-2010, 02:56 PM)Argorate a écrit : Curiosité: C'est basé sur quel algo cette fonction?
C'est écrit dans les notes, sous les exemples…
Documentation PHP de sort() a écrit :Note: Like most PHP sorting functions, sort() uses an implementation of » Quicksort.
(06-05-2010, 02:56 PM)Argorate a écrit : Moi je vois rien contre, mais justement une partie de la question c'est es-ce qu'il y a mieux?
D'autant plus qu'il n'est pas donnée la Complexité asymptotique au pire des cas. C'est dur de comparé au niveau performance quand on ne donne pas la complexité
Tu dis avoir moins de 5 nombres à trier. Est-ce réellement utile de considérer les performances, dans un tel cas ?
Une implémentation d'un algorithme — même supposé plus efficace (je doute qu'un algorithme soit plus efficace qu'un autre sur un échantillon si petit) — arrivera-t-elle à dépasser les performances d'une fonction native ?
Sephi-Chan
RE: Le meillieur algo de tri pour des nombres? - Melimelo - 06-05-2010
Sur des échantillons si petit la différence de performance doit vraiment être minimes si pas inexistante ...
RE: Le meillieur algo de tri pour des nombres? - Argorate - 06-05-2010
C'est pas une question de performance effective mais de performance théorique. Quitte a faire les choses autant les faire bien, donc justement j'étais curieux de savoir l'outil le plus approprié dans ce cas.
PS: effectivement j'avais pas vu que ça venait du Quicksort, ça peut donc être assez intéressant.
Si j'y pense (et si je le temps) je regarderais si c'est plus rapide que l'implémentation pur et dure du Quicksort que j'avais fait il y a quelques mois.
Merci, pour le moment ça me convient vu les performances de Quicksort.
RE: Le meillieur algo de tri pour des nombres? - Sephi-Chan - 06-05-2010
Ah ok, c'était de la branlette quoi !
Sephi-Chan
RE: Le meillieur algo de tri pour des nombres? - Allwise - 06-05-2010
(06-05-2010, 02:28 PM)Argorate a écrit : J'aurais préféré un avis parce que tu as déjà était dans un cas similaire^^
Surtout que je suis dans un cas très simple < 5 éléments.
Donc c'est sans doute pas la peine de déployer un quickshort juste pour ça non?
Tu cherches l'algo de tri le plus rapide sur de petits échantillons de données. Je te donne un article qui compare la performance des algos de tri sur de petits, moyens, et grands volumes. What the buck ?
Je me suis jamais posé la question parce que je ne trie jamais des tableaux de plusieurs milliers d'enregistrements. Pour l'usage courant les fonctions natives me suffisent, je m'attarde pas à chercher de la perf sur ça, pour les petits volumes y a rien à prendre...
Comme dit Sephi, je doute qu'il y ait plus rapide que les fonctions natives du langage sur des petites taches comme ça.
Pour des traitements plus lourds ça vaut le coup de se poser la question. Mais un petit tri ça passe comme une lettre à la poste
