ALGOS DE TRI EN VB
cs_Willi
Messages postés
2375
Date d'inscription
jeudi 12 juillet 2001
Statut
Modérateur
Dernière intervention
15 décembre 2018
-
17 avril 2006 à 14:43
us_30 Messages postés 2065 Date d'inscription lundi 11 avril 2005 Statut Membre Dernière intervention 14 mars 2016 - 20 avril 2006 à 17:45
us_30 Messages postés 2065 Date d'inscription lundi 11 avril 2005 Statut Membre Dernière intervention 14 mars 2016 - 20 avril 2006 à 17:45
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.
https://codes-sources.commentcamarche.net/source/37093-algos-de-tri-en-vb
https://codes-sources.commentcamarche.net/source/37093-algos-de-tri-en-vb
20 avril 2006 à 17:45
Oui... bien... l'algorithme nommé "Tri panier", est en fait identique à celui que je nomme "Counting Sort"... Soit dit en passant, le "tri Insertion" nommé comme cela sur le site où je me suis informé (en Rem dans le code), se révèle être le "tri Sélection" !... LA valse des noms ! Y'a pas trop de rigueur là-dans !
Ta remarque sur l'allocation mémoire est juste, j'en suis conscient. Le meilleur choix algorithmique, dépendra du type de données à trier...
JE t'invite à refaire un petit tour quand j'aurai un peu plus fait mûrir cette présentation...
A+,
Amicalement,
Us.
20 avril 2006 à 11:39
POURQUOI: CountingSort alloue un tableau temporaire, si donc on a besoin de perfs c'est que les tableaux peuvent être très grands et en ce cas cette méthode est à exclure car la mémoire peut manquer alors que le QuickSort de mon exemple fonctionnera à tout coup. Un vrai logiciel ne peut pas se permettre d'avoir un doute sur le résultat, il doit trier toujours s'il est fait pour cela.
Jette un oeil sur la discussion en comments de cette source:
http://www.cppfrance.com/codes/QUICKSORT-NON-RECURSIF_36347.aspx
20 avril 2006 à 11:18
- T'as qu'à attacher une carotte au bout d'un bâton. Grimpe sur son dos, et met lui devant le nez !
- Non, non... je préfère continuer à tirer comme un bourricot.
(normal pour un âne...)
Salut BruNews,
JE ne crois pas être de ton avis. Je me demande même si tes propos reflète vraiment ton opinion, tant que cela me paraît inconsistant. Certes, si on veut intrinsèquement plus rapide, on peut utiliser le C. Mais cela doit-il empêcher à chercher un algorithme rapide, parce que c'est du VB ? c'est idiot !
Et tu nous diras si je me trompe, mais la comparaison d'algorithmes dans un langage, vaut dans tous les langages, pour peu que de la différence soit significative. Non ?
Tu noteras, que je ne prends pas beaucoup de risque en te disant cela, car la raison même de la mesure de la complexité d'un algorithme repose justement sur la mesure du nombre d'opérations (pour faire simple). Or, que ce soit en VB ou en C, cette mesure est toujours bien respectée?
Ensuite, tu remarqueras que les longueurs de codage sont équivalentes, et qu'il en sera toujours un peu près ainsi, cela te satisfait peut-être, mais ce n'est pas pour moi un critère. De plus, la simplicité algorithmique est une notion bien trop humaine, pour être aussi un critère. Les choses deviennent simples dès qu'elles sont comprises?
Maintenant, si on respecte ton raisonnement, parce qu'on est en VB d'une part, et qu'il faut un codage court et simple de compréhension, d'autre part, on a plus comme choix le tri à bulle ! C'est à dire, quasiment, le moins performant ! ! ? ce n'est pas malin, tu l'auras compris.
Pour ton QuickSort en C, il est un peu prés 22 fois plus rapide qu'en VBA. Mais, si je compare avec mon CountingSort proposé et en VBA, il n'est plus que de 3,6 fois plus rapide. Donc, hors problème de typage des données, un bon choix algorithmique peut donner un résultat plus qu'honorable ! c'est justement le sens de mes propos?
Amicalement,
Us.
18 avril 2006 à 23:08
Je ne suis pas convaincu qu'un algo de tri en vb doit être performant, je pense que sa simplicité et sa petite taille en code doivent primer.
Si on a vraiment besoin de perfs alors on compile un quicksort en C dans une dll et on lui refile le boulot, les temps seront à coup sur incomparables.
Je ne peux pas tester ton prog cause que je n'ai pas de runtime vb mais si tu veux essayer:
http://bnmvp.free.fr/SortInt.zip
J'ai invalidé l'affichage pour ne mesurer que le tri (en millisecondes), il y a options de trier 100 000 ou 1000 000 éléments, tu nous diras.
Vois que c'est dispo pour compile en dll, juste à prendre le code de Sorter.cpp et en faire une dll qui exportera QuickSort(int *base, unsigned int num).
18 avril 2006 à 22:36
Bien vu ! je mettrai à jour avec ta remarque.
Pour les 2 algos, BUBBLE SORT et Tri à bulle, ce sont presque les mêmes... presque, mais pas exactement les mêmes. L'Algo Tri à bulle est la version de base. Pour l'autre, j'ai mis ma petite touche personnelle, avec une idée toute simple augmentant la vitesse d'environ 40% par rapport à la version de base. C'est la raison pour laquelle je l'ai baptisé en anglais... Comme quoi, de petites remarques peut faire une grande différence...
JE pense qu'il serait bon que je détaille un peu le fonctionnement de chaque algo, afin qu'on puisse se repérer...
En effet, si pour certaines appellations les algos trouvés sur internet sont les mêmes, pour d'autre, en revanche, cela recouvre plusieurs types d'algorithmes, et, j'avoue, de fait, me perdre un peu dans les noms, à cause de cette ambiguïté... A titre d'illustration, j'ai trouvé un autre algo aussi appelé Counting Sort, beaucoup moins performant.
De plus, leurs domaines d'emploi et des tests de performances systématiques sont aussi des renseignements très utiles, que je n'ai jamais trouvé !
Sans compter, qu'on trouve difficilement ces algorithmes en VB !? ... ou alors, j'suis toujours tombé à côté -:);
Mon idée étant justement de classer un peu ces différents algorithmes, pour en ressortir que les meilleurs dans leurs genres, avec la meilleur optimisation possible, afin de choisir en connaissance de cause.
En effet, trier des listes arrive de temps en temps, et c'est quasiment toujours un point critique dans l'exécution d'un programme. Un algorithme lent où mal adapté pouvant gravement pénaliser une application...
Si vous avez déjà ou connaissez des algorithmes de tri prêt à l'emploi (en VB !), j'suis preneur afin de les passer à la moulinette !
Merci, A+
Amicalement,
Us.
18 avril 2006 à 12:08
c'est excellent, ce truc là... j'avais lu un truc la dessus, y'a quelques années (dans le livre du dragon rouge, je crois)...
sa vitesse provient du fait que l'on ne fait aucune comparaison (à part pour déterminer les min/max), pour effectuer le tri
à noter qu'il devient lent si la gamme de valeur est grande et qu'il ne fonctionne tel quel que pour des valeurs entières...
tu pourrais éviter deux tests, encore :
Mini = t(NBmin)
Maxi = t(NBmin)
For i = NBmin + 1 To NBmax
j = t(i)
If Mini > j Then
Mini = j
End If
If Maxi < j Then
Maxi = j
End If
Next i
18 avril 2006 à 10:35
Pas la peine de mettre les deux.
J'ai fait des tests de performance, dont voici les résultats :
Taille d'un tableau triable en 1 seconde (sur mon PC actuel, variable selon la puissance du PC, mais les ordres de grandeurs entre les différents tris seront gardés)
Bubble : 2 600
Insertion : 6 100
QuickSort : 250 000
CountingSort : 1 700 000
En clair, dès que le tableau dépasse les 5000 éléments, oubliez Insertion et surtout Bubble.
CountingSort est quasi instantané (0.04 secondes) pour 100 000 éléments.
Mais il est toujours bon de savoir que tout çà existe.
17 avril 2006 à 14:57
Merci 10/
17 avril 2006 à 14:43
Pour ce genre de code dépose les plutôt sur www.codyx.org.
Bonne continuation.