TRI PAR INSERTION

Commentaire de Galain le 13/03/2010 23:35:30

Intéresses-toi au tri Quick Sort qui est beaucoup plus rapide

Commentaire de jmc70 le 14/03/2010 17:34:35

Effectivement, un Quicksort est capable de trier 50000 éléments en moins de 2 sec, mais ce qui m'intéresse c'est de pouvoir stocker les doublons à part et j'ai du mal à gérer cela dans la recursivité du Quicksort. Je ne connais pas l'introsort et je vais faire quelques recherches car c'est peut-être la solution à mon problème (tester par dichotomie si l'élément est présent avant de lancer le tri récursif). Si j'ai le temps, je mettrai en ligne le source modifié. Merci donc à Galain et TarodMaster.

Commentaire de jmc70 le 14/03/2010 19:52:20

J'ai mis le source modifié en ligne.
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).

Commentaire de Galain le 14/03/2010 20:50:27

Salut
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

Commentaire de Galain le 14/03/2010 20:58:20

' les indices 0 et dernier du tableau sont nécessaires
' 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

Commentaire de BILLOTmi le 15/03/2010 09:55:24

Je ne pense pas qu'une collection ameliorerait la vitesse mais alourdirait plutot vu le code supplementaire a executer.
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

Commentaire de jmc70 le 15/03/2010 18:20:06

@Billotmi
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.

Commentaire de Galain le 16/03/2010 00:58:48

Salut JMC70
J'ai oublié : la routine Quicksort que tu as programmée est incorrecte

Commentaire de jmc70 le 20/03/2010 17:55:07

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.