Tri par insertion

Soyez le premier à donner votre avis sur cette source.

Vue 8 468 fois - Téléchargée 902 fois

Description

Les listes triées sont très pratiques pour des quantités de données limitées : une liste semble pouvoir contenir plus de 32767 éléments (il faudrait les compter pour être sûr, en tout cas, on n'a pas de message d'erreur) mais liste.listcount retourne systématiquement un nombre signé codé sur 16 bits, donc compris entre -32768 et +32767 ce qui rend les éléments excédentaires inaccessibles.
Pour traiter de grandes quantités de données on doit donc recourir à un tableau. Le plus simple consiste à trier le tableau au fur et à mesure de sa création, ce qui équivaut à un tri par insertion.
La limite théorique est alors d'un peu plus de 2 milliards d'items.

Conclusion :


Cet exemple est destiné aux débutants et permet de se familiariser avec les tableaux dynamiques (dim, redim, preserve, ubound, erase...)
Le temps de traitement qui passe, sur ma vieille machine, de 6 sec pour 10000 chaînes à 96 sec pour 50000 augmente plus vite que le nombre d'éléments à traiter. Cela vient du fait qu'il faut décaler vers le haut un certain nombre d'éléments à chaque insertion. Une optimisation doit être possible à ce niveau et m'intéresserait.

Codes Sources

A voir également

Ajouter un commentaire

Commentaires

CGSI3
Messages postés
416
Date d'inscription
vendredi 22 février 2008
Statut
Membre
Dernière intervention
7 janvier 2018
1
Voici juste si vous avez le temps d'essayer ce code avec lequel je tri 20000 Elts en 0.7 sec sur mon vieux PC
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
cs_Galain
Messages postés
1263
Date d'inscription
mardi 11 novembre 2003
Statut
Membre
Dernière intervention
24 juillet 2013
6
Salut JMC70
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
JMC70
Messages postés
77
Date d'inscription
samedi 9 novembre 2002
Statut
Membre
Dernière intervention
6 juillet 2014

J'ai donc modifié le source à partir de l'idée de Galain qui m'a d'ailleurs envoyé un programme corrigé, ce dont je le remercie.
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.
michelpiesyk
Messages postés
1
Date d'inscription
jeudi 19 novembre 2009
Statut
Membre
Dernière intervention
14 janvier 2011

bonjour,

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
cs_Galain
Messages postés
1263
Date d'inscription
mardi 11 novembre 2003
Statut
Membre
Dernière intervention
24 juillet 2013
6
Salut JMC70
J'ai oublié : la routine Quicksort que tu as programmée est incorrecte

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.