Le tri par casiers
Description
Le TRI PAR CASIERS ( bucket sort ) très simple et très rapide avait été snobé au début de la micro-informatique pauvre en mémoire-vive notamment parce qu'il est gourmant en mémoire lorsque il est utilisé pour le tri de valeurs numériques. Mais comme de nos jours le moindre micro dispose généralement de plusieurs Go dans ses barrettes, autant en profiter.
Principe du tri par casiers : Un tableau trié n'est rien d'autre que la restitution, dans l'ordre d'apparition des occurrences des valeurs, du tableau non trié :
Exemple de table à trier : 34, 55, 88, 55, 99, 55
- Dimensionnement d'une table de comptage 'nbOcc' des occurences : Maxi des valeurs = 99 et Mini = 34 donc SetLength(nbOcc,99-34+1)
- Comptages : nbOcc(34)=1, nbOcc(55)=3, nbOcc(88)=1, nbOcc(99)=1
- Restitution : 1 fois 34 suivi de 3 fois 55 suivi de 1 fois 88 suivi de 1 fois 99
ce qui donne 34, 55, 55, 55, 88, 99 = tableau trié en seulement trois temps.
Ce code permet de comparer les performances du tri par casiers à celles du QuickSort :
1) Cas du tri de valeurs entières :
1.1) Cas d'utilisation-idéal : Tris de valeurs du type Word avec tableau de comptage du type Statique :
- pour trier 200000 valeurs : Tri_Casiers_Word mis : 0 ms, QuickSortRecursif mis : 31 ms
- pour trier 2000000 valeurs : Tri_Casiers_Word mis : 0 ms, QuickSortRecursif mis : 187 ms
- pour trier 20000000 valeurs : Tri_Casiers_Word mis : 0 ms, QuickSortRecursif mis : 1591 ms
- pour trier 200000000 valeurs : Tri_Casiers_Word mis : 0 ms, QuickSortRecursif mis : 16177 ms
- Et comme la résolution des GetTickCount's utilisés pour le chronométrage est de 16 ms on peut conclure que
Tri_Casiers_Word est jusqu'à 16177/16 = 1011 fois plus rapide que ce QuickSort !!!
1.2) Exemples avec Maxi des valeurs = 1000000 et Mini = 0, connus à l'avance et transmis (utilisation semi-optimale) :
- pour trier 1000000 valeurs : Tri_Casiers_LongWord 7,8 fois plus rapide que QuickSort Récursif
- pour trier 10000000 valeurs : Tri_Casiers_LongWord 17,3 fois plus rapide que QuickSort Récursif
- pour trier 1000000 valeurs : Tri_Casiers_LongWord 6,2 fois plus rapide que QuickSort Itératif
- pour trier 10000000 valeurs : Tri_Casiers_LongWord 15,1 fois plus rapide que QuickSort Itératif
1.3) Exemples avec Maxi des valeurs à rechercher d'abord par boucle : Tri par casiers entre 2,4 et 8,1 fois plus rapide que le QuickSort Itératif.
2) Cas du tri de chaînes de caractères : Dans ce cas la taille de la table de comptage des occurrences d'un même caractère ne dépasse pas 256 et la valeur maxi d'un caractère ne dépasse pas 255 donc peu gourmand en mémoire et comme on le sait à l'avance ça va déjà dans le sens d'une utilisation optimale ... Donc on trie une première fois sur le premier caractère et on isole dans une sous-liste les chaînes qui commencent par la même SubString ... puis on trie cette sous-liste sur le 2ième caractère et on isole comme déjà dit ... et ainsi de suite jusqu'à la fin de chaque chaîne ... mais on peut aussi se contenter de limiter la profondeur-max du tri aux N premiers caractères des chaînes : gain de speed variable supplémentaire.
Exemples de perfs. avec des tris de chaînes toutes de 250 caractères et profondeur de tri = 250 :
- pour 500000 chaînes : Tri par casiers 26,9 fois plus rapide que QuickSort Récursif
- pour 1000000 chaînes : Tri par casiers 27,8 fois plus rapide que QuickSort Récursif.
D'où ce code ... juste pour le fun ...
1) Pour les tris de valeurs du type Word comme pour les tris de chaînes de caractère : le tri par casiers est nettement plus rapide que les QuickSort : EXIT les QuickSort.
2) Pour les tris de valeurs du type LongWord et Integer, comme la mem-vive-adressable sous Delphi-32bits est limitée à 4 Go, le tri par casiers reste utilisable lorsque l'écart ValeurPlafond - ValeurPlancher des valeurs à trier est connu et tel que la création du tableau des occurrences ne sature pas la mémoire-disponible, et dans ce cas :
- Tri_Casiers_LongWord et Tri_Casiers_Int ne sont plus rapides que QuickSortRecursif que si le Nombre de Valeurs à trier est supérieur à environ 0,03 fois
la Taille du tableau de comptage des occurrences,
- et pour Tri_Casiers_Int_Stat ce coefficient de 0,03 descend à 0,0095,
... mais, après tout, on ne recherche des gains de vitesse que lorsqu'on a affaire à un nombre élevé de valeurs !
Sous Delphi-64bits on devrait pouvoir profiter encore davantage de la vitesse du tri par casiers vu la taille de la mem-vive-adressable sous 64 bits...
Principe du tri par casiers : Un tableau trié n'est rien d'autre que la restitution, dans l'ordre d'apparition des occurrences des valeurs, du tableau non trié :
Exemple de table à trier : 34, 55, 88, 55, 99, 55
- Dimensionnement d'une table de comptage 'nbOcc' des occurences : Maxi des valeurs = 99 et Mini = 34 donc SetLength(nbOcc,99-34+1)
- Comptages : nbOcc(34)=1, nbOcc(55)=3, nbOcc(88)=1, nbOcc(99)=1
- Restitution : 1 fois 34 suivi de 3 fois 55 suivi de 1 fois 88 suivi de 1 fois 99
ce qui donne 34, 55, 55, 55, 88, 99 = tableau trié en seulement trois temps.
Ce code permet de comparer les performances du tri par casiers à celles du QuickSort :
1) Cas du tri de valeurs entières :
1.1) Cas d'utilisation-idéal : Tris de valeurs du type Word avec tableau de comptage du type Statique :
- pour trier 200000 valeurs : Tri_Casiers_Word mis : 0 ms, QuickSortRecursif mis : 31 ms
- pour trier 2000000 valeurs : Tri_Casiers_Word mis : 0 ms, QuickSortRecursif mis : 187 ms
- pour trier 20000000 valeurs : Tri_Casiers_Word mis : 0 ms, QuickSortRecursif mis : 1591 ms
- pour trier 200000000 valeurs : Tri_Casiers_Word mis : 0 ms, QuickSortRecursif mis : 16177 ms
- Et comme la résolution des GetTickCount's utilisés pour le chronométrage est de 16 ms on peut conclure que
Tri_Casiers_Word est jusqu'à 16177/16 = 1011 fois plus rapide que ce QuickSort !!!
1.2) Exemples avec Maxi des valeurs = 1000000 et Mini = 0, connus à l'avance et transmis (utilisation semi-optimale) :
- pour trier 1000000 valeurs : Tri_Casiers_LongWord 7,8 fois plus rapide que QuickSort Récursif
- pour trier 10000000 valeurs : Tri_Casiers_LongWord 17,3 fois plus rapide que QuickSort Récursif
- pour trier 1000000 valeurs : Tri_Casiers_LongWord 6,2 fois plus rapide que QuickSort Itératif
- pour trier 10000000 valeurs : Tri_Casiers_LongWord 15,1 fois plus rapide que QuickSort Itératif
1.3) Exemples avec Maxi des valeurs à rechercher d'abord par boucle : Tri par casiers entre 2,4 et 8,1 fois plus rapide que le QuickSort Itératif.
2) Cas du tri de chaînes de caractères : Dans ce cas la taille de la table de comptage des occurrences d'un même caractère ne dépasse pas 256 et la valeur maxi d'un caractère ne dépasse pas 255 donc peu gourmand en mémoire et comme on le sait à l'avance ça va déjà dans le sens d'une utilisation optimale ... Donc on trie une première fois sur le premier caractère et on isole dans une sous-liste les chaînes qui commencent par la même SubString ... puis on trie cette sous-liste sur le 2ième caractère et on isole comme déjà dit ... et ainsi de suite jusqu'à la fin de chaque chaîne ... mais on peut aussi se contenter de limiter la profondeur-max du tri aux N premiers caractères des chaînes : gain de speed variable supplémentaire.
Exemples de perfs. avec des tris de chaînes toutes de 250 caractères et profondeur de tri = 250 :
- pour 500000 chaînes : Tri par casiers 26,9 fois plus rapide que QuickSort Récursif
- pour 1000000 chaînes : Tri par casiers 27,8 fois plus rapide que QuickSort Récursif.
D'où ce code ... juste pour le fun ...
Source / Exemple :
Voir le ZIP
Conclusion :
1) Pour les tris de valeurs du type Word comme pour les tris de chaînes de caractère : le tri par casiers est nettement plus rapide que les QuickSort : EXIT les QuickSort.
2) Pour les tris de valeurs du type LongWord et Integer, comme la mem-vive-adressable sous Delphi-32bits est limitée à 4 Go, le tri par casiers reste utilisable lorsque l'écart ValeurPlafond - ValeurPlancher des valeurs à trier est connu et tel que la création du tableau des occurrences ne sature pas la mémoire-disponible, et dans ce cas :
- Tri_Casiers_LongWord et Tri_Casiers_Int ne sont plus rapides que QuickSortRecursif que si le Nombre de Valeurs à trier est supérieur à environ 0,03 fois
la Taille du tableau de comptage des occurrences,
- et pour Tri_Casiers_Int_Stat ce coefficient de 0,03 descend à 0,0095,
... mais, après tout, on ne recherche des gains de vitesse que lorsqu'on a affaire à un nombre élevé de valeurs !
Sous Delphi-64bits on devrait pouvoir profiter encore davantage de la vitesse du tri par casiers vu la taille de la mem-vive-adressable sous 64 bits...
Codes Sources
A voir également
- Le tri par casiers
- Tri calcul ✓ - Forum Visual Basic 6
- Tri par insertion java - Forum Java
- Tri par base ✓ - Forum Delphi / Pascal
- Tri radix ✓ - Forum C
- Tri Radix (Tri par base) - Forum C
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.