LE TRI PAR CASIERS
cs_pseudo3
Messages postés
268
Date d'inscription
mardi 24 juillet 2007
Statut
Membre
Dernière intervention
2 février 2021
-
13 avril 2012 à 09:56
cs_pseudo3 Messages postés 268 Date d'inscription mardi 24 juillet 2007 Statut Membre Dernière intervention 2 février 2021 - 26 avril 2012 à 10:15
cs_pseudo3 Messages postés 268 Date d'inscription mardi 24 juillet 2007 Statut Membre Dernière intervention 2 février 2021 - 26 avril 2012 à 10:15
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/54213-le-tri-par-casiers
https://codes-sources.commentcamarche.net/source/54213-le-tri-par-casiers
26 avril 2012 à 10:15
>> "Il semble donc qu'à un certain stade les temps d'accès à la mémoire prennent le pas sur le calcul pur !" :
... Avec un collègue qui tricote à merveille l'ASM on recherchait ces derniers temps des astuces pour gagner en speed, et on vient de constater que lorsque le rapport NombreDeValeurs/(ValeurPlafond-ValeurPlancher+1) c.à.d le rapport NombreDeValeurs/TailleDuTableauDesOccurrences est très faible c'est la durée du SetLength de dimensionnement de ce tableau qui est supérieur à la durée du tri ...
Face à ce constat, deux tactiques possibles :
- soit on considère, qu'après tout on ne recherche les gains de speed que lorsque le NonbreDeValeurs à trier est très élevé, et dans ce cas on conserve le principe d'utiliser un tableau dynamique pour le comptage des occurrences,
- soit on remplace ce tableau par un tableau statique et on gagne la durée du SetLength que le NombreDeValeurs soit faible ou important.
On a donc remplacé ce tableau par un tableau statique dans l'un des tris_casiers et voici des extraits des résultats de tests comparatifs de vitesse :
1.1) Pour trier 20 000 000 nombres allant de 0 à 65535 :
Tri_Casiers_Word mis : 0 ms
QuickSortRecursif mis : 1545 ms
QuickSortIteratif mis : 1357 ms
1.2) Pour 200 000 000 nombres allant de 0 à 65535 :
Tri_Casiers_Word mis : 0 ms
QuickSortRecursif mis : 15943 ms : 15 943 fois plus lent !!!
QuickSortIteratif mis : 13915 ms
Sans le SetLength le Tri_Casiers_Word a déjà terminé alors que les Quick sont à peine sortis des starting-blocs et pédalent dans la choucroute à faire leurs comparaisons et leurs swaps.
>> "Dans le cas des casiers, il s'agit plus d'une indexation que d'un tri (le tri n'étant que la conséquence de l'indexation)" :
... Effectivement les valeurs va:=VAL[i] - ValPlancher deviennent les indices du tableau de comptage des occurrences.
>> "retrouver instantanément un appelant à partir de son numéro de téléphone" :
Le casier cubique et votre hyper-cube ont-ils un rapport avec ce sujet ???
Cordialement, et à +.
25 avril 2012 à 17:17
Il semble donc qu'à un certain stade les temps d'accès à la mémoire prennent le pas sur le calcul pur !
Je ne vois qu'une seule application possible : la recherche coûte que coûte du meilleur temps de calcul possible. Dans le cas des casiers, il s'agit plus d'une indexation que d'un tri (le tri n'étant que la conséquence de l'indexation).
C'est le lot commun de tout moteur de base de données : répondre le plus vite possible à une requête...
Exemple très concret (en tout cas pour moi puisque je travaille pour les pompiers): retrouver instantanément un appelant à partir de son numéro de téléphone.
A ma connaissance, le plus extraordianire est un moteur de recherche comme G...e
La codification, le tri, l'indexation des informations est un secret à 195 594.93 MUSD
Je doute pas que toutes les techniques soient soigneusement étudiées et testées...
25 avril 2012 à 10:31
>> "j'obtiens 15s avec Quicksort et 4s avec le cube" : donc tri-casier-cubique 3,75 fois plus "Quick" que le Quicksort.
>> "Quicksort reste une solution universelle et efficace" : Exact, l'avantage du QuickSort réside dans le fait que ses contraintes d'utilisation sont peu nombreuses et qu'on peut l'utiliser pour trier presque n'importe quoi et son seul point faible est qu'il n'est pas toujours le plus rapide bien que sa vitesse peut être parfois jugée suffisante par certains.
Pour ma part j'ai horreur des barres de progression qui me disent "Patience je pédale" (lol)
Ceci étant, j'ai un faible pour le tri par casiers : Hyper-simple et vraiment rapide lorsque ses contraintes d'utilisation sont réalisables et compatibles avec les besoins d'un projet.
Petite question à propos du "tri avec un casier cubique 256 * 256 * 256" : A quoi peut servir un tel tri dans la pratique ???
Cordialement, et à +.
24 avril 2012 à 19:29
un tri avec un casier cubique 256 * 256 * 256 (excusez du peu...)
Pour me simplifier la vie, la liste de base est composée de chaines de 3 caractères tirés au hasard, ce qui est une condition très favorable pour ce type de tri.
Pour 2 000 000 chaines dans la liste,
j'obtiens 15s avec Quicksort et 4s avec le cube.
Le problème essentiel est que Quicksort sait comparer directement deux chaines de caractères, alors que pour le tri par casier, il faut récupérer la valeur ASCII de chaque caractère...
Compte tenu des contraintes, le résultat ne me semble pas exeptionnel, mais ça peut être intéressant si on est pile poil dans le cas de figure qui va bien.
Quicksort reste une solution universelle et efficace.
24 avril 2012 à 16:27
Ah, bon, merci, ça éclaire ma lanterne. C'est fou tout ce qui peut être trié !!!
A12C4
24 avril 2012 à 15:50
C'est une base de données qui contient (en plus des textes et des nombres) des point, des lignes et des surfaces. Même Oracle a une extension SIG...
Du coup, on a des requêtes semblables à ce qu'on trouve en SQL mais en plus rigolo :
Au lieu de X<Y, on a P INCLU_DANS S
ou bien P A_UNE_DISTANCE_INFERIEURE_A 20m DE S
Bien sur, on peut mélanger les deux :
Quels sont les bâtiments de type "ECOLE" LES_PLUS_PROCHES_DU bâtiment "Mon_Domicile"
Ou encore : TRIER les casernes de pompiers LES_PLUS_PROCHES de l'incendie...
Evidement, pour être efficace l'index "spatial" n'est pas un des types connus...
24 avril 2012 à 14:48
Oups, j'ai écrit > C'est "qui" les "SIG" ??? Je rectifie : C'est quoi les "SIG" ???
A+.
24 avril 2012 à 14:46
"Tri géographique" : Tiens je ne m'attendais pas un éventuel besoin du type trier un territoire... mais après tout dès qu'on a de chiffres et/ou des lettres on peut trier.
C'est qui les "SIG" ???
L'idée de ma méthode à 256 casiers récursifs pour les chaînes de caractères m'est venue via le point faible du tri par casiers gourmand en mémoire pour le tri de valeurs numériques ... mais avec seulement 256 valeurs pour les caractères je me suis dit qu'au moins dans tel cas le besoin en mem-vive n'est plus un problème, donc vu la rapidité du tri par casiers autant en profiter pour trier des chaînes et du coup ce tri est environ 27 fois plus "Quick" que le Quick_Sort_Récursif ... et autant en faire profiter les autres.
Pour y arriver l'utilisation des sous-listes du type TStringList m'a bien simplifié la vie, mais peut-être qu'une astuce permettrait d'améliorer encore les performances ...
Cordialement, et à+.
24 avril 2012 à 13:54
Ca me rapelle un tri "géographique" que j'ai écrit il y a quelques années. L'objectif était de trier un territoire suivant le critère "XY" (abcisse/ordonnée, latitude/longitude,...) Et effectivement la méthode par casiers s'est avérée très efficace, en particulier pour traiter les notions de "voisinage".
La méthode maintenant retenue pour les SIG est le quadtree qui n'est autre qu'une "simplification" à 4 casiers récursifs.
Votre méthode à 256 casiers récursifs pour les chaînes de caractères est en quelques sortes une 256tree. (probablement plus efficace qu'une Btree...)
En fait, je parle de tri, mais il serait plus juste de parler d'indexation, le tri n'étant qu'une des possibilités offertes par une indexation correcte.
18 avril 2012 à 12:26
Pour ceux que ça intéresse, voici la version du Tri_Casiers pour le tri de valeurs négatives mélangées à des valeurs positives.
Mais attention gros problème de débordement de RAM si on veut trier des nombres allant -MaxInt à +MaxInt !!! (car dans ce cas la taille du tableau des occurrences est alors égale à 2*MaxInt+1).
Par contre avec ma bécane je profite de la rapidité du Tr_Casiers pour des nombres allant de -100000000 à +100000000 ce qui peut être suffisant dans beaucoup de cas.
procedure Tri_Casiers_Int(var T : array of integer; vPlaf, vPlan : integer; sens2tri : boolean);
// Tri par casiers pour nombres négatifs et/ou positifs
// En entrée vPlaf = 0 signifie "valeur-Plafond ET valeur-Plancher inconnus"
// par contre si vPlaf et vPlan sont correctement donnés en entrée cela fait gagner le temps
// que prendrait la recherche des valeurs maxi et mini dans le tableau T
var nbOcc : array of integer; va,i,j,k : integer;
begin
// Etape 1 : Recherche éventuelle du maxi vPlaf et du mini vPlan si vPlaf est nul en entrée :
if vPlaf = 0 then
begin vPlan := T[0];
for i := Low(T) to High(T) do
begin if T[i] >= vPlaf then vPlaf := T[i] else if T[i] <= vPlan then vPlan := T[i]; end;
end;
SetLength ( nbOcc, vPlaf-vPlan+1); // Dimensionnement du tableau des occurrences
// Etape 2 : Recherche des nombres d'occurrences dans le tableau des valeurs à trier :
for i := Low(T) to High(T) do nbOcc[ T[i]-vPlan ] := nbOcc[ T[i]-vPlan ] + 1;
// Etape 3 : Restitution :
k := Low(T);
if sens2tri = true then // Restitution en ordre croissant :
begin for va :=vPlan to vPlaf
do if nbOcc[va-vPlan] <> 0 then for j :=1 to nbOcc[va-vPlan] do begin T[k] := va; inc(k); end;
end else // Restitution en ordre décroissant :
begin for va := vPlaf downto vPlan
do if nbOcc[va-vPlan] <>0 then for j :=1 to nbOcc[va-vPlan] do begin T[k] := va; inc(k); end;
end;
SetLength ( nbOcc, 1);
end;
A+.
16 avril 2012 à 16:51
Si t'as des remarques à faire après tes vérifications, surtout n'hésites pas.
Je viens d'essayer de créer une variante simplifiée du Tri_CasiersStr(var DonneesTxt: tStringList; ProfMaxTri: integer; SensDeTri: boolean) dans laquelle j'ai remplacé la gymnastique avec les sous-listes par du HashCode de string mais comme les HashCodes renvoient des nombres énormes cela engendre une table d'Occurences de taille énorme (débordement de capacité) dès que la longueur des chaînes dépasse 5 : donc je l'ai mise à la poubelle.
Quicksort : Il reste incontournable pour le tri de valeurs numériques réelles.
A+.
16 avril 2012 à 09:57
Je pensai que le Quicksort était globalement le plus stable et le plus performant dans la pluspart des cas? Ton code mérite donc quelques vérifications...
Je le regarderai avec intérêt...
Merci pour ta contribution
Jean_Jean
13 avril 2012 à 09:56
Si quelqu'un trouve une astuce pour augmenter encore davantage la vitesse d'exécution de la procedure Tri_CasiersStr(var DonneesTxt: tStringList; ProfMaxTri: integer; SensDeTri: boolean) surtout n'hésitez pas à la signaler ici.
a+.