TRI PAR INSERTION
Profil bloqué
-
13 mars 2010 à 23:35
CGSI3 Messages postés 416 Date d'inscription vendredi 22 février 2008 Statut Membre Dernière intervention 7 janvier 2018 - 2 avril 2010 à 17:42
CGSI3 Messages postés 416 Date d'inscription vendredi 22 février 2008 Statut Membre Dernière intervention 7 janvier 2018 - 2 avril 2010 à 17:42
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/51439-tri-par-insertion
https://codes-sources.commentcamarche.net/source/51439-tri-par-insertion
2 avril 2010 à 17:42
Elle peut avoir un interet sur des listes déja pré trié ou trié.
Dim Liste() as string
Redim Liste(1 to 20000) as string (ou Long)
Public Sub Tri_Vague(Liste) 'tri 1 dimension de 1 à x
'Auteur: CGSI3
'But: tri une liste selon Methode par Vagues
' derivée du tri a bulle
' Le but est de trier des éléments distants et de
' se rapprocher du tri a bulle
Dim c As Long, b As Long, Cpt As Long, Cp2 As Long, Ok As Boolean, oX As Boolean, oZZ As Boolean
Mt GetTickCount: oX False: b = LBound(Liste, 1): c = UBound(Liste, 1)
EcartMem (c - b) \ 2: ecart EcartMem: oZZ = True
Do
If oZZ And ecart > 10 Then
'oZZ permet d'alterner Ecart=ecartement
ecart Int(EcartMem / 1.7): EcartMem ecart
Else: ecart = ecart - 1
End If
If ecart < 3 Then ecart = 2
Ok True: oZZ Not (oZZ): Cp2 = ecart - 1
For Cpt = ecart To c
f Cpt - Cp2: T Liste(f)
If T > Liste(Cpt) Then
Liste(f) Liste(Cpt): Liste(Cpt) T: Ok = False
End If
Next Cpt
Loop Until Ok And ecart = 2
End Sub
Cordialement CGSI3
21 mars 2010 à 17:39
Ta source est pas mal
Un petit bémol : un Doevents en dehors d'une boucle For,Do ou While ne sert strictement à rien
For i = 0 to 10000
Doevents <-- ici c'est Ok
.................
.......
.........
Next
20 mars 2010 à 17:55
Si j'ai le temps je reprendrai l'algo de MichelPiesyk en l'adaptant aux listes (plus besoin de tableau) et en m'affranchissant du principe alphabétique, ce qui pourrait donner :
- dès qu'une liste atteint 32000 éléments, on la divise en deux listes en transférant la moitié des éléments dans la seconde (le point faible de l'algo !) ;
- on met à jour une table de hachage qui contient les premier et dernier élément de chaque liste ;
- lors d'un ajout, on cherche dans la table de hachage dans quelle liste doit aller le nouvel élément ;
- on vérifie qu'il n'y est pas déjà (sinon, doublon), puis on l'ajoute (en réalité, l'insère puisque la liste est automatiquement triée par sorted=true) ;
- etc.
Je pense néanmoins que le dernier algo qui est dans le source peut difficilement être dépassé (50000 éléments en 4 secondes) et je remercie tous les participants pour leurs idées.
17 mars 2010 à 09:25
En modifiant un peu le tri par dichotomie, c'est a dire:
le tri simple compare 2 données et les inverse ou pas, si je mets ce tri a bosser sur 180.000 enregistrements complexes on est a 3'25" sur un pc 2.2 giga bi-coeur.
Je passe à 1'25" apres ma modif:
principe: le traitement de 180.000 articles est trop long, le tri de 5000 articles est beacoup plus rapide. partant de cette constatation, je decoupe les 180.000 enregistrements en paquet de 5000, je tri chaque paquet, et je fusionne, voila le principe.
Pour ton tri par insertion, je ferais une petite table a coté, dans laquelle je mets la 1ere lettre du champ ex: "A" et un pointeur sur le premier a de ta liste. Tu extrais la premiere lettre du champ, tu la cherche ds la petite table en tu as directement l'adresse dans la liste du premier elemnt portant cette lette, ce qui evite de tester tous les eleme,nts precedents, tu comprae ton string pour l'inserer, si tu as rupture sur le premier caractere tu stop ta recherche. Conclusion pour la recherche de "ftghu" tu ne teste que les données commencant par un "f", ce qui t'evite toutes les precedentes: Plus tu as de données plus tu gagnes du temps.
Salut
Michel
16 mars 2010 à 00:58
J'ai oublié : la routine Quicksort que tu as programmée est incorrecte
16 mars 2010 à 00:02
J'ai regardé ton code et on peut y faire de sacrées optimisations
voici celles que j'ai trouvées
1) Ne rendre les listes visibles que lorsque leur affichage est complètement terminé
2) Gérer le Listcount des listes si il est négatif
3) Ne pas dépasser 65535 comme taille du tableau d'origine
4) et celle-ci est la plus importante : un 3° algo de tri super rapide qui respecte l'ordre d'entrée des doublons
On associe au nombre entré une clef indiquant son numéro d'entrée dans le tableau : ex 0052480012 (les 4 derniers indique que le nombre 005248 a été entré en douzième position)
ainsi avec le tri Quicksort tous les nombres sont triés et les doublons sont triés selon l'ordre d'entrée.
Donc en séparant le nombre et sa clef d'entrée et avec l'exemple suivant
002485 0012
002485 0056
002485 0069
Le premier n'est pas un doublon car c'est le premier entré dans le tableau
Les autres ont été entrés ensuite et sont des vrais doublons du premier
et pour 50000 éléments je retrouve mes 4 ou 5 secondes de traitement
si cela t'intéresse envoie-moi un message en privé avec ton émail et je te fournirai le code que j'ai pondu
Sur cela a+ et bonne prog et vive codes-sources
15 mars 2010 à 18:20
J'ai donc ajouté l'algo qui utilise une chaîne de caractères pour rechercher les doublons puis je la transforme en tableau que je trie par le QuickSort. Les performances restent cependant inférieures à l'algorithme d'origine. A la fin, la transformation en tableau par split() puis le Quicksort n'ont qu'un effet minime sur la performance(j'ai fait un essai en les supprimant, pour ne garder que la recherche des doublons) : visiblement, c'est la constitution de la chaîne puis la recherche par instr() qui prennent du temps.
15 mars 2010 à 11:39
j'avais pensé au tableau fixe avec une variable correspondant au nombre d'éléments réels, variable incrémentée à chaque ajout. Or j'ai constaté que le Redim Preserve est vraiment peu gourmand en ressources car les différences de traitement sont négligeables de l'ordre de quelques secondes) :
- pour 10000 chaînes -> 5 sec au lieu de 6
- pour 30000 chaînes -> 41 sec au lieu de 42
- pour 50000 chaînes -> 94 sec au lieu de 96
comme on perd la souplesse du tableau dynamique, j'ai donc préféré conserver le redim preserve.
------
La méthode avec QuickSort est ici tout à fait anecdotique et c'était pour répondre @Galain car je ne l'ai ajoutée après coup (l'intérêt du tri par insertion est justement de se passer... d'un tri).
A vrai dire, le tri ici n'est utile que pour pouvoir effectuer une recherche dichotomique d'un éventuel doublon qui n'est possible... que lorsque le tableau est trié.
L'intérêt de l'algorithme que j'ai déposé ici vient du fait qu'il permet de connaître en une seule opération s'il s'agit d'un doublon (et dans ce cas de le traiter à part) ou sinon de récupérer l'indice d'insertion de l'enregistrement dans le tableau.
Le problème de la lenteur vient du "comment décaler un tableau vers le haut" rapidement. VB sait le bien le faire en quelques secondes quand on remplit une liste ou une combo triée jusqu'à 32000 éléments.
Maintenant, il n'y a peut-être pas d'autre solution que de patienter.
----------
L'utilisation de instr sur une chaîne de caractères semble prometteuse. J'ai fait simplement un essai avec :
a$ = String(40000, "12345") + "67890" + String$(10000, "12345")
MsgBox Str$(InStr(a$, "67890"))
et la recherche est pratiquement instantané. En générant une chaîne de 500 millions de caractères cela prend quelques secondes, l'élément à chercher se trouvant aux 9/10 de la chaîne ; au delà j'ai un message d'erreur pour mémoire insuffisante.
Si j'ai le temps, j'essaierai d'ajouter cet algo au programme (mais dans ce cas, il ne s'agira plus d'un tri - simplement une recherche des doublons, ce qui correspond d'ailleurs à mon problème initial).
15 mars 2010 à 09:55
Par contre je tenterais plutot deux optimisations .
1°) Optimisation 1 valable pour les deux methodes
afin d'éviter le preserve hatif du tableau complet a chaque insertion d'un element, je dimensionnerais au depart le tableau à la taille maxi et je gererais moi meme dans une variable le nombre d'éléments chargés dans le tableau. Quitte a la fin a faire un Redim Preserve avec le Nb d'éléments reels pour recuperer de la place memoire. (Attention a l'impact sur la recherche dichotomique et sur le tri : UBOUND ne pointe plus le dernier element chargé mais le dernier alloué)
2°) Optimisation 2 pour la methode avec QuickSort
Plutot que de faire un QuickSort apres chaque insertion, je gererais un index dans une chaine de caractere afin de determiner si la clé existe ou pas et je ne trierai le tableau qu'une seule fois à la fin du chargement.
Exemple :
' Initialisation index
Dim IndexKey$
IndexKey$='|"
' Ajout d'une Clé a charger (Key$)
If Instr(Indexkey$,"|" & Key$ & "|") = 0 Then
' Mise a jour de l'index (non trié mais sans doublon)
IndexKey$ = IndexKey$ & Key$ & "|"
' Traitement nouvelle clé
Else
' Traitement doublon
ENDIF
' Un seul quicksort a la fin
15 mars 2010 à 08:52
La Collection interdisant les doublons, on pourrait gérer une liste de doublons dans un tableau, en utilisant une gestion d'erreur, disons...
14 mars 2010 à 20:58
' mais ne contiendront pas d'élément valide.
Ces 2 lignes de commentaire ne servent plus à rien : elles proviennent de la source déposée par JMC70
14 mars 2010 à 20:56
14 mars 2010 à 20:50
avec ce code j'obtiens un temps de 4 secondes pour créer un tableau de 40000 entrées "chaines de caractères", trier le tableau par Quicksort et afficher les 2 listes
La form ne change pas au niveau des contrôles
Option Explicit
' Le tableau dynamique est utilisé globalement pour une meilleure rapidité
Dim Table() As String
Private Sub Btn_Commencer_Click()
Dim i As Long, simple As Long, doublon As Long
Dim Début As Date
' les indices 0 et dernier du tableau sont nécessaires
' mais ne contiendront pas d'élément valide.
ReDim Table(0 To 39999)
Liste.Clear
Liste_Doubles.Clear
Screen.MousePointer = 11
Début = Time
Liste.Visible = False
Liste_Doubles.Visible = False
' ------------------------
' on crée le tableau de 40000 chaînes de caractères générées aléatoirement
For i = 0 To 39999
DoEvents
Table(i) = Format$(Rnd * 100000, "000000")
Next i
' On trie le tableau en Quicksort
Tri_QuickSort 0, UBound(Table)
' on transfère le tableau dans les listes pour le visualiser
Liste.AddItem Table(0) doublon 0: simple 1
For i = 1 To UBound(Table())
DoEvents
If Table(i) = Table(i - 1) Then
Liste_Doubles.AddItem Table(i)
doublon = doublon + 1
Else
Liste.AddItem Table(i)
simple = simple + 1
End If
Next i
Liste.Visible = True
Liste_Doubles.Visible = True
Etiq_Temps.Caption = "Durée : " + Format$(Time - Début, "hh:mm:ss")
' Affichage
Etiq_Nombre.Caption = Str$(simple)
Etiq_Doubles.Caption = Str$(doublon)
MsgBox "Traitement fini", vbOKOnly
' l'effacement du tableau est nécessaire pour libérer la mémoire attribuée.
Erase Table()
End Sub
Sub Tri_QuickSort(Debuttable As Long, Fintable As Long)
' le paramètre Debut correspond au numéro du premier élément à trier (à l'appel il vaut 0)
' le paramètre Fin correspond au numéro du dernier élément à trier (à l'appel il vaut Nb_Element -1)
Dim i As Long
Dim j As Long
' I et J sont des variables intermédiaires utilisées pour les compteurs de boucles
Dim chainemilieu As String
' chainemilieu est une variable intermédiaire utilisée pour la comparaison d'éléments
Dim chainetampon As String
' chainetampon est une variable intermédiaire utilisée pour la permutation d'éléments
i = Debuttable&
j = Fintable&
chainemilieu = Table(((Debuttable& + Fintable&) \ 2))
Do
DoEvents
While Table(i) < chainemilieu
i = i + 1
Wend
While chainemilieu < Table(j)
j = j - 1
Wend
If i <= j Then
chainetampon = Table(i)
Table(i) = Table(j)
Table(j) = chainetampon
i = i + 1
j = j - 1
End If
Loop Until i > j
' Une fois le tri précédant effectué, on rappelle la fonction en changeant les bornes.
If Debuttable& < j Then
Tri_QuickSort Debuttable&, j
End If
If i < Fintable& Then
Tri_QuickSort i, Fintable&
End If
End Sub
14 mars 2010 à 20:18
Par contre si ton tableau est déjà trié c'est très rapide de déterminer si tu as un doublon, il faut juste comparer avec la "case" précédente de ton tableau. C'est vraiment si long de trier d'abord?
14 mars 2010 à 19:52
Je dois respecter une contrainte qui est que les doubles doivent être refusés d'entrée dans la liste (et non pas enlevés après le tri par une recherche des doubles). J'ai donc testé le QuickSort après chaque ajout d'enregistrement mais les performances sont nettement dégradées par rapport à l'idée d'origine car un QuickSort, tout récursif qu'il soit, reste nettement plus lent qu'un décalage séquentiel d'enregistrements vers le haut. J'ai consulté l'article de Wikipedia sur l'Introsort, mais ce n'est qu'une amélioration du Quicksort qui ne changerait rien au problème. Lequel reste posé - si quelqu'un a une idée.
A vrai dire j'ai réalisé ce petit programme pour un module de suppression des fichiers doublons sur un disque dur d'archives (même nom, date et taille parmi plusieurs centaines de milliers de fichiers - eh oui ! les archives s'accumulent au fil du temps et on duplique souvent des dossiers entiers alors qu'il n'y a qu'un fichier modifié dedans) : or il faut que le premier fichier trouvé soit considéré comme "le bon" et les autres comme des doublons à supprimer. Je peux mettre le programme en ligne si ça intéresse quelqu'un (mais je crois qu'on en trouve déjà sur Code Source).
14 mars 2010 à 17:58
Pour simplifier : http://fr.wikipedia.org/wiki/Introsort
Mais attention l'algorithme décrit sur cette page a quelques erreurs. A lire avec précaution^^
14 mars 2010 à 17:34
14 mars 2010 à 14:38
Surtout c'est l'idée: "Le plus simple consiste à trier le tableau au fur et à mesure de sa création, ce qui équivaut à un tri par insertion.", qui me questionne. Est-ce vrai? Et est-ce que "le plus simple" est le plus efficace ou le plus rapide? En terme de tri on ne s'intéresse pas au tri le plus simple sinon on serait tous au tri bulle^^, mais aux tris les plus efficaces ou les plus rapides.
13 mars 2010 à 23:35