Les bibliothèques de langage C bien connues incluent newlib et glibc. Je pense que la fonction qsort est utilisée depuis plus de 20 ans. Il y a quelques inconvénients.
１．newlib qsort dans newlib ne trie que directement et ne passe pas automatiquement au tri indirect. Par conséquent, il est lent lorsque les éléments du tableau d'origine sont volumineux. (Tri indirect: créez un tableau de pointeurs vers chaque élément et triez-le. Enfin, déplacez les éléments du tableau d'origine.)
２．glibc Le qsort de la glibc est en fait un tri par fusion. Donc c'est rapide quand les clés sont uniques (comme les numéros d'employés), Si la clé a des doublons (comme homme / femme), elle est lente. De plus, puisqu'il s'agit d'un tri de fusion, il s'agit d'un tri stable. Cependant, lorsque l'allocation de la zone de travail (malloc) échoue Faites un tri rapide normal. Par conséquent, la "stabilité" ne peut être garantie.
Le ss18 sorti cette fois est un tri rapide et stable. Si vous voulez un "tri rapide car instable" Nous recommandons ss15 (http://ww51.tiki.ne.jp/~srr-cake/qsort/qs15/).
newlib ・ glibc Je n'ai pas fait beaucoup de recherches de façon inattendue. Veuillez me faire savoir s'il existe un tri de comparaison plus rapide.
ss18 nécessite une zone de travail (ordre $ O (n) $) (= tableau auxiliaire). qsort de la glibc utilise le même espace de travail $ O (n) $ même si sa stabilité n'est pas garantie. L'auteur pense que c'est bien à une époque où la mémoire principale est bon marché.
Dans qsort, le pire temps de calcul est $ O (n ^ 2) $. Cependant, puisque SS18 sélectionne soigneusement le pivot, Presque aucune séquence cible de tri incompatible (se produit par hasard ou par malchance) penser.
Cependant, le temps de calcul est $ O (n ^ 2) $ pour un tableau créé de manière malveillante à trier. Peut être. En guise de contre-mesure, "sélectionnez le pivot plus soigneusement" Tu peux. (Cependant, il n'est pas implémenté dans la version actuelle) Plus précisément, "Lorsque le premier ss18 est appelé dans le processus, avec la fonction time (), etc. Générez un nombre aléatoire non reproductible et faites varier le pivot avec cette valeur. " Cette méthode est particulièrement utile pour ssort, qui est un tri stable. Même si le pivot fluctue En effet, le tableau cible sera toujours le même après le tri. Cela peut être différent dans qsort.
C'est un algorithme complètement différent du ss14 précédemment publié. C'est plus compact et plus rapide. Grosso modo ss18 répète les mouvements suivants dans la séquence auxiliaire (ptr2) et la séquence cible (ptr).
ptr2:............... → ptr2:5555......77787 → ptr2:..........77787
ptr :357358257257237 Ａ ptr:332223......... Ｂ ptr:3322235555.....
Version simplifiée pour l'explication de l'algorithme (taille d'élément fixée à 8 octets) (ss18c4d) Le temps de traitement mesuré est indiqué ci-dessous. La version simplifiée du programme est répertoriée à la fin.
Type de clé Nombre d'éléments Taille Nombre de répétitions Temps de traitement(Secondes)
qs_glibc d=-3 e=10000 s=8 R2463 T=5.74
ss18c4d d=-3 e=10000 s=8 R2463 T=4.73
qs_glibc d=100 e=10000 s=8 R7035 T=15.47
ss18c4d d=100 e=10000 s=8 R7035 T=6.25
qs_glibc d=2 e=10000 s=8 R24630 T=35.19
ss18c4d d=2 e=10000 s=8 R24630 T=2.35
d=-3:Aucune clé en double d=100:100 types de clés d=2:La clé, ce sont les hommes et les femmes, etc.
Nombre d'itérations: nombre d'itérations de tri pour réduire les erreurs de mesure du temps de traitement
qs_glibc est une modification de la fonction qsort de la bibliothèque C "glibc" pour la mesure des performances. qs_glibc fonctionne comme un tri de fusion sauf si malloc () échoue. Le tri par fusion est un tri stable (https://ja.wikipedia.org/wiki/sort). Dans tous les cas, ss18c4d est plus rapide que qs_glibc. La version standard (ss18e8b) peut être trouvée à http://ww51.tiki.ne.jp/~srr-cake/qsort/ss18/.
J'ai posté la méthode de la version régulière du test de référence dans readme2.txt. La version régulière mesure également le temps de traitement de qsnewlib. (Voir http://ww51.tiki.ne.jp/~srr-cake/qsort/ss18/bench-sample.txt)
qsnewlib est la fonction qsort de la bibliothèque C "newlib". Tri instable. Il n'est donc pas surprenant que qsnewlib soit le plus rapide, mais au tri indirect Qsnewlib est lent lorsque la taille de l'élément est grande car il n'y a pas de commutation automatique.
Comparaison de qsnewlib (instable) qs_glibc (stable) ss18e8b (stable) Pour les systèmes 64 bits, ss18e8b est généralement le plus rapide.
/********** ssort (stable sort) ss18 *******/
/*
Version simplifiée de SS18(ss18 est un tri de comparaison stable. Plus rapide que le tri par fusion et ss14.)
Tableau cible(ptr)Et séquences auxiliaires(ptr2)(Même taille que ptr)Effectuez un tri stable à l'aide de.
Déplacez l'élément dans l'étape AB2 comme suit. Ici "5" est le pivot(Élément divisé)Représente.
ptr2:............... → ptr2:5555......77787 → ptr2:..........77787
ptr :357358257257237 Ａ ptr:332223......... Ｂ ptr:3322235555.....
Dans le mouvement A, les pivots sont rassemblés au bord gauche de ptr2, les éléments inférieurs à 5 sont rassemblés au bord gauche de ptr2,
Collectez les éléments supérieurs à 5 sur le bord droit de ptr2. A ce moment, 77787 est dans l'ordre inverse de l'ordre initial.
Au moment du mouvement B, si 5555 est dans l'ordre inverse, le 5555 immédiatement après B est déplacé dans l'ordre avant.
À ce stade, le 5555 est déjà dans la position terminée triée.
Puis 332223{Position de départ / position finale / ordre avant / arrière}Vers la pile.
Après cela, le même processus est répété pour 77787. Si le tableau partiel a une longueur de 2 ou moins, le tri partiel est terminé.
De la pile{Position de départ / position finale / ordre avant / arrière}Est retiré et le traitement se poursuit.
Le processus se termine lorsque la pile devient vide.
(Puisque ce qui précède est une version simplifiée, la position de rangement du pivot est différente de la version régulière)
*/
#include <stdio.h>
//typedef long unsigned int size_t;
void *malloc(size_t); void free(void*); void exit(int);
static void assert(int x, char *s) //Si nécessaire, décommentez la ligne ci-dessous
{ /* if (x) return; fprintf(stderr, "++++ %s ++++\n", s); exit(1); */ }
#define F(x) (*((long long int *)(x)))
#define COPY(x,y) { F(x)=F(y); } /*Copier le traitement des éléments du tableau*/
#define SWAP(x,y) {long long int v=F(x); F(x)=F(y); F(y)=v;} /*Traitement de permutation des éléments de tableau*/
//Les trois lignes ci-dessus sont liées au mouvement des éléments et peuvent être réécrites sur une autre.
//Ci-dessous le programme de tri par ss18
typedef struct { char *LLss, *RRss; int Rv; } stack_node; /*L,Structure de la pile qui empile R*/
#define PUSH(llss,rrss,rv) {top->LLss = (llss); top->RRss = (rrss); top->Rv = (rv); ++top;} /*Empiler*/
#define POP(llss,rrss) {--top; llss = top->LLss; rrss = top->RRss; rev = top->Rv;} /*revenir*/
int ssort( void *base, size_t nel, size_t size, int (*cmp)(void *a, void *b) )
/* base :Pointeur vers le tableau que vous souhaitez trier*/
/* nel :Nombre d'éléments dans la base du tableau*/
/* size :Taille de l'élément de la base du tableau (en octets)*/
/* cmp :Un pointeur vers une fonction qui compare la taille des éléments*/
{
char *l,*l0,*r,*r0,*L,*R; // l0,r0,L,R est le point de départ à gauche et à droite du tableau. L'élément entre L et R est l,r,Trier par m
char *ptr,*ptrE,*ptr2; // ptr,ptr2 est L ~ R,La première émission et la première réception du réseau 10 à r0 sont commutées à chaque fois.
char *m,*m0,*p; //p se déplace entre L et R*Accumuler les pivots en m
int t, rev; //t est pour le travail rev==Lorsqu'il vaut 0, l'ordre entre L et R est normal.
long long int Z; //Z est la distance entre les tableaux(Peut être positif ou négatif)
stack_node stack[32], *top = stack; /*32 c'est assez pour l'instant*/
assert(sizeof( int) == 4, "sizeof( int) == 4");
assert(sizeof(long long int) == 8, "sizeof(long long int) == 8");
assert(size == 8 , "Puisqu'il s'agit d'une version simplifiée, la taille est fixée à 8." );
//Puisqu'il s'agit d'une version simplifiée, l'alignement de la base est sizeof(char*)Supposons que ce soit
ptr2 = malloc( nel * size ); //ptr2 est un tableau auxiliaire pour le tri
if (ptr2 == NULL) {assert(0,"malloc a échoué"); return 1;}
ptr = base;
Z = ptr2 - ptr; //Z a des distances positives et négatives entre deux tableaux et tableaux auxiliaires
ptrE = ptr + nel * size; //ptrE est utilisé pour déterminer si L à R sont dans la séquence cible ou la séquence auxiliaire.
L=ptr; R=&ptr[size*(nel-1)]; rev=0;
goto LOOP;
//Jusqu'à présent, un appel à ssort n'est exécuté qu'une seule fois
nxt:
if (stack == top) {free(ptr2); return 0;} /*Quitter lorsque la pile est vide*/
POP(L,R); /*Obtenez la valeur sur la pile*/
LOOP:
if (R<L) { /*Aucun élément*/
goto nxt;
}
if (L==R) { /*Nombre d'éléments 1*/
if (ptr<=L && L<ptrE) { } // L<Le jugement de ptr2 est normal, mais ptr2<Il existe également un système de base
else {COPY(L-Z,L)}
goto nxt;
}
if (L+size==R) { /*Nombre d'éléments 2*/
if ((t=cmp(L,R))<0) if (ptr<=L && L<ptrE) { }
else {COPY(L-Z,L) COPY(R-Z,R)}
else if (t>0) if (ptr<=L && L<ptrE) {SWAP(L,R) }
else {COPY(L-Z,R) COPY(R-Z,L)}
else if (ptr<=L && L<ptrE) if (rev==0) { }
else {SWAP(L,R) }
else if (rev==0) {COPY(L-Z,L) COPY(R-Z,R)}
else {COPY(L-Z,R) COPY(R-Z,L)}
goto nxt;
}
if (ptr<=L && L<ptrE) {l=l0=L ; r=r0=R+Z; m=m0=L+Z;} // l :Où placer ensuite les éléments plus petits que le pivot
else {l=l0=L-Z; r=r0=R-Z; m=m0=L; } // r :Où placer ensuite les éléments plus grands que le pivot
// m :Où mettre ensuite le même élément que le pivot
COPY(m,L) m+=size; //Puisqu'il s'agit d'une version simplifiée, faites simplement pivoter le premier élément
for (p=L+size; p<=R; p+=size) {
if ((t=cmp(p,m0))<0) {COPY(l,p) l+=size;}
else if (t>0) {COPY(r,p) r-=size;}
else {COPY(m,p) m+=size;}
}
assert((l-l0)+(m-m0)+(r0-r)==(R-L+size),"(l-l0)+(m-m0)+(r0-r)Est étrange");
if (rev==0) {
p=l; do {COPY(p,m0) m0+=size; p+=size;} while (m0<m); //Il y en a au moins un en m0-m
if (l-l0 < r0-r) {PUSH(r+size,r0,1) L=l0; R=l-size; rev=0;} /*Trier de gauche à droite*/
else {PUSH(l0,l-size,0) L=r+size; R=r0; rev=1;} /*Trier de la droite au premier*/
}else{
p=l; do {m-=size; COPY(p,m) p+=size;} while (m0<m); //Il y en a au moins un en m0-m
if (l-l0 < r0-r) {PUSH(r+size,r0,0) L=l0; R=l-size; rev=1;} /*Trier de gauche à droite*/
else {PUSH(l0,l-size,1) L=r+size; R=r0; rev=0;} /*Trier de la droite au premier*/
}
goto LOOP;
}
Recommended Posts