XL 2013 les machistes (utilisateurs de Mac OS peuvent ils tester ceci

[patricktoulon]

Bonjour à tous
@RyuAutodidacte m' a rappelé un lien vers un amis de l'autre monde concernant une classe pseudo dictionnaire pour MAC
malgré que j'apprécie beaucoup l'auteur (avec qui j'ai même collaboré sur l’accélérateur de requête entre autres ) ,je trouve que c'est un peu usine à gaz

j'ai donc fait les choses à ma façon
mais avant d'aller plus loin car des idées j'en ai plein ,si vous êtes un utilisateur sur MAC pouvez vous tester ce pseudo dictionnaire
sur Windows ça match il me faut confirmation sur MAC

Merci pour vos retours

 

[patricktoulon]

re
Bonjour @Dranreb
c'est un peu ce que fait le quicksort ça finalement

dans cette description pour python c'est clairement le quicksort qui est expliqué

L'algorithme de recherche dichotomique dans un tableau trié - myMaxicours

Objectifs Comprendre l’algorithme de recherche dichotomique dans un tableau trié. Étudier la terminaison et la correction de cet algorithme. Points clés La recherche...

www.maxicours.com

 

[Dranreb]

Ben non, à ma connaissance, dans sa version de base, l'algorithme du QuickSort continue jusqu'au bout d'intervertir bêtement les éléments rapprochés au lieu de basculer vers un tri par insertion qui devient alors le plus performant.

 

[RyuAutodidacte]

avec la partie temp je te l'ai dis je suis 0.70/0.80
je les ai testé toutes les 3
celle de hier reste ta meilleure

J’ai 0,31 cf post 371

 

[patricktoulon]

je pense avoir pigé un peu le principe mais avec un tableau trié
mais je ne vois pas l'utilisation de la recherche dichotomique là dedans
nous ce que l'on cherche c'est trier un array désordoné numerique ou string
si tu a un exemple je suis preneur

en tout ca pour la recherche j'ai pigé le truc

 

[RyuAutodidacte]

au lieu de basculer vers un tri par insertion qui devient alors le plus performant.

Quelque part sur ce que j'ai fait c'est une sorte d'insertion trié propre à chaque ensemble qui ont une partie commune fait sur une boucle avant le tri final

 

[RyuAutodidacte]

je pense avoir pigé un peu le principe

oui j'ai fait un tableau supp ou je ne mets que les clé, je tri ce tableau supp avec le même fonction et grace au clé je récupère le n° de ligne pour remettre tous les arrays dans l'ordre

 

[patricktoulon]

je garde celle d'hier quand même

 

[RyuAutodidacte]

je garde celle d'hier quand même

Tu l’as testé ?? pour voir si cela réduit le temps aussi de ton côté … ?

 

[patricktoulon]

purée ça m'enerve(mais ça me plait)
@Dranreb m'a posé une colle là
comment utiliser la recherche dichotomique et quel est l'intérêt de l'utiliser pour trier un tableau désordoné

 

[patricktoulon]

ben oui j'ai testé bien sur même encore toute à l'heure

je te dis que la meilleure c'est celle d'hier

sincèrement

modele0(hier) -->Mac 0.45/0.50 windows a peu pres pareil à 2 poil de cator près

model(1,2,3)--> Mac 0.31/0.30 window 0.70/0.80

tu choisirais de publier quoi toi ?
donc non je te le redis je kiffe pas là
grosssomodo tu a remplacé un insertBubble par ta boucle temp(je simplifie la chose)
et ben sur windows c'est plus lourd
pas compliqué à comprendre
donc pour moi version 1 ,2 ,3 = poubelle je garde la version 0

 

[Dranreb]

comment utiliser la recherche dichotomique et quel est l'intérêt de l'utiliser pour trier un tableau désordoné

C'est pourtant évident: à partir de 2 éléments rangés dans l'ordre on a une partie déjà classée dans laquelle on peut faire une recherche dichotomique pour savoir où insérer le 3ième, et ainsi de suite. Ça économise les comparaisons mais pas les déplacements. C'est pour ça que le gain de temps se gâte pour des morceaux au delà d'une quarantaine d'éléments, mais bien plus, vers le millier, si on peut utiliser le MoveMemory pour les effectuer.

 

[patricktoulon]

bonjour ryu
je crois avoir compris pourquoi chez toi c'est plus rapide
en fait j'ai testé deux listes de nombre
liste 1 > 10 000 items de 1 à 30 000 donc les nombres ne se suivent pas forecement
liste 2 > 10 000 items de 1 à 10 000 dans le désordre

liste 1 > 0.45 sec
liste 2 > 0.13 sec

@Dranreb ok je comprends le raisonnement
mais pour le mettre en oeuvre ouf !

 

[RyuAutodidacte]

bonjour ryu
je crois avoir compris pourquoi chez toi c'est plus rapide
en fait j'ai testé deux listes de nombre
liste 1 > 10 000 items de 1 à 30 000 donc les nombres ne se suivent pas forecement
liste 2 > 10 000 items de 1 à 10 000 dans le désordre

Hello Patrick
j'ai pris la liste qui se trouve dan le fichier des recueils de tri

@Dranreb @patricktoulon

@Dranreb ok je comprends le raisonnement
mais pour le mettre en oeuvre ouf !

Oui c'est clair

à partir de 2 éléments rangés dans l'ordre on a une partie déjà classée dans laquelle on peut faire une recherche dichotomique pour savoir où insérer le 3ième, et ainsi de suite.

C'est dans le cas de 2 éléments rangés, mais comment fais ton pour savoir qu'il y en a déjà 2 d'éléments rangés
En plus dans mes recherches ça parle de recherche dichotomique dans une liste trié
Alors oui je comprends le principe de recherche pour faire le moins d'interventions et mettre directement les éléments à leur place
Dans le cas ou il y a aucun éléments trié, il faudrait alors prendre un ou 2 élément de références et faire les recherche via cette base
Mais bon en effet c'est pas évident

 

[Dranreb]

Bonjour.
C'est inutile : on n'entame jamais une partition de QuickSort de moins de 2 éléments de Min à Max.
En considérant le 1er à sa bonne place provisoire, on peut déjà trouver où va le second avec ce bout de code :

      For R = Min + 1 To Max: Arg = TDon(R)
         Mn = Min: Mx = R
         Do: S = (Mn + Mx) \ 2
            If TDon(S) <= Arg Then Mn = S + 1 Else Mx = S
            Loop Until Mx <= Mn
         For S = R To Mn + 1 Step -1: TDon(S) = TDon(S - 1): Next S
         TDon(S) = Arg
         Next R

Contexte :

Private Sub PartitAmél(TDon(), ByVal Min As Long, ByVal Max As Long)
   Dim VPiv, Crs As Long, Dcr As Long, V, _
      R As Long, Arg, Mn As Long, Mx As Long, S As Long
   If Max - Min > 20 Then
      VPiv = TDon(Min + Int(Rnd * (Max - Min + 1)))
      Crs = Min: Dcr = Max
      Do While Crs <= Dcr
         Do While TDon(Crs) < VPiv: Crs = Crs + 1: Loop
         Do While VPiv < TDon(Dcr): Dcr = Dcr - 1: Loop
         If Crs <= Dcr Then
            V = TDon(Crs): TDon(Crs) = TDon(Dcr): TDon(Dcr) = V
            Crs = Crs + 1: Dcr = Dcr - 1
            End If
         Loop ' While Crs <= Dcr
      If Crs < Max Then PartitAmél TDon, Crs, Max
      If Min < Dcr Then PartitAmél TDon, Min, Dcr
   Else
      For R = Min + 1 To Max: Arg = TDon(R)
         Mn = Min: Mx = R
         Do: S = (Mn + Mx) \ 2
            If TDon(S) <= Arg Then Mn = S + 1 Else Mx = S
            Loop Until Mx <= Mn
         For S = R To Mn + 1 Step -1: TDon(S) = TDon(S - 1): Next S
         TDon(S) = Arg
         Next R
      End If
   End Sub

 

[patricktoulon]

j'ai mis la source a jour