Mejorando el tipo rápido
https://stackoverflow.com/questions/1688264
-
18-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Si es posible, ¿cómo puedo mejorar el siguiente tipo rápido (en cuanto al rendimiento)? ¿Alguna sugerencia?
void main()
{
quick(a,0,n-1);
}
void quick(int a[],int lower,int upper)
{
int loc;
if(lower<upper)
{
loc=partition(a,lower,upper);
quick(a,lower,loc-1);
quick(a,loc+1,upper);
}
}
/* Return type: int
Parameters passed: Unsorted array and its lower and upper bounds */
int partition(int a[],int lower,int upper)
{
int pivot,i,j,temp;
pivot=a[lower];
i=lower+1;
j=upper;
while(i<j)
{
while((i<upper)&&(a[i]<=pivot))
i++;
while((a[j]>pivot))
j--;
if(i<j)
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}//end while
if(pivot>a[j])
{
temp=a[j];
a[j]=a[lower];
a[lower]=temp;
}
return(j);
}//end partition
Solución
El algoritmo de Quicksort es fácilmente paralelo. Si tiene múltiples núcleos con los que trabajar, podría ver un poco de velocidad. Dependiendo de cuán grande sea su conjunto de datos, podría proporcionarle fácilmente más velocidad que cualquier otra optimización. Sin embargo, si solo tiene un procesador o un conjunto de datos relativamente pequeño, no habrá mucha velocidad.
Podría explicar más si esto es una posibilidad.
Otros consejos
- Elija un mejor pivote: por ejemplo. En la mediana de tres, eliges 3 elementos (aleatorios) y eliges el pivote como elemento mediano
- Cuando la longitud (a []) <m (en la práctica elija M = 9) deje de clasificar. Después de Qsort () terminado, aplicar insertar el sort de inserción que tomaría aproximadamente m * n = o (n). Esto evita muchas llamadas de funciones cerca de la hoja del árbol de recursión de divide-et-impera.
La primera sugerencia sería: reemplazar una de las llamadas recursivas con iteración. Y me refiero a la iteración real, no una pila implementada manualmente para la recursión. Es decir, en lugar de hacer dos "nuevas" llamadas a quick de quick, "recicla" tu Actual llamar a quick para procesar una rama de la recursión y llamar quick recursivamente para procesar otra rama.
Ahora, si te aseguras de que siempre haces una llamada recursiva real para el corto Partición (y usar iteración para el más largo), garantizará que la profundidad de la recursión nunca exceda log N Incluso en el peor de los casos, es decir, independientemente de qué tan bien elijas tu mediana.
Todo esto se implementa en qsort Algoritmo que viene con la biblioteca estándar GCC. Eche un vistazo a la fuente, debería ser útil.
Aproximadamente, una implementación más práctica que sigue la sugerencia anterior podría verse como sigue
void quick(int a[], int lower, int upper)
{
while (lower < upper)
{
int loc = partition(a, lower, upper);
if (loc - lower < upper - loc)
{ /* Lower part is shorter... */
quick(a, lower, loc - 1); /* ...process it recursively... */
lower = loc + 1; /* ...and process the upper part on the next iteration */
}
else
{ /* Upper part is shorter... */
quick(a, loc + 1, upper); /* ...process it recursively... */
upper = loc - 1; /* ...and process the lower part on the next iteration */
}
}
}
Esto es solo un boceto de la idea, por supuesto. No probado. Nuevamente, eche un vistazo a la implementación de GCC para la misma idea. También reemplazan la llamada recursiva restante con recursión "manual", pero no es realmente necesario.
La clasificación de pequeños bloques (<5 elementos) con un algoritmo sin bucle puede mejorar el rendimiento. Encontré solo un ejemplo de cómo escribir un algoritmo de clasificación sin bucle para 5 elementos: http://wiki.tcl.tk/4118
La idea se puede usar para generar algoritmos de clasificación sin bucle para 2,3,4,5 elementos en C.
Editar: lo probé en un conjunto de datos y medí el 87% de tiempo de ejecución en comparación con el código en la pregunta. El uso de inserción en el tipo de <20 bloques resultó en un 92% en el mismo conjunto de datos. Esta medición no es representativa, pero puede mostrar que esta es una forma en que puede mejorar su código QuickSort.
Editar: este código de ejemplo Escriba las funciones de clasificación sin bucle para 2-6 elementos:
#include <stdio.h>
#define OUT(i,fmt,...) printf("%*.s"fmt"\n",i,"",##__VA_ARGS__);
#define IF( a,b, i, block1, block2 ) \
OUT(i,"if(t[%i]>t[%i]){",a,b) block1 OUT(i,"}else{") block2 OUT(i,"}")
#define AB2(i,a,b) IF(a,b,i,P2(i+2,b,a),P2(i+2,a,b))
#define P2(i,a,b) print_perm(i,2,(int[2]){a,b});
#define AB3(i,a,b,c) IF(a,b,i,BC3(i+2,b,a,c),BC3(i+2,a,b,c))
#define AC3(i,a,b,c) IF(a,c,i, P3(i+2,c,a,b), P3(i+2,a,c,b))
#define BC3(i,a,b,c) IF(b,c,i,AC3(i+2,a,b,c), P3(i+2,a,b,c))
#define P3(i,a,b,c) print_perm(i,3,(int[3]){a,b,c});
#define AB4(i,a,b,c,d) IF(a,b,i,CD4(i+2,b,a,c,d),CD4(i+2,a,b,c,d))
#define AC4(i,a,b,c,d) IF(a,c,i, P4(i+2,c,a,b,d), P4(i+2,a,c,b,d))
#define BC4(i,a,b,c,d) IF(b,c,i,AC4(i+2,a,b,c,d), P4(i+2,a,b,c,d))
#define BD4(i,a,b,c,d) IF(b,d,i,BC4(i+2,c,d,a,b),BC4(i+2,a,b,c,d))
#define CD4(i,a,b,c,d) IF(c,d,i,BD4(i+2,a,b,d,c),BD4(i+2,a,b,c,d))
#define P4(i,a,b,c,d) print_perm(i,4,(int[4]){a,b,c,d});
#define AB5(i,a,b,c,d,e) IF(a,b,i,CD5(i+2,b,a,c,d,e),CD5(i+2,a,b,c,d,e))
#define AC5(i,a,b,c,d,e) IF(a,c,i, P5(i+2,c,a,b,d,e), P5(i+2,a,c,b,d,e))
#define AE5(i,a,b,c,d,e) IF(a,e,i,CB5(i+2,e,a,c,b,d),CB5(i+2,a,e,c,b,d))
#define BE5(i,a,b,c,d,e) IF(b,e,i,AE5(i+2,a,b,c,d,e),DE5(i+2,a,b,c,d,e))
#define BD5(i,a,b,c,d,e) IF(b,d,i,BE5(i+2,c,d,a,b,e),BE5(i+2,a,b,c,d,e))
#define CB5(i,a,b,c,d,e) IF(c,b,i,DC5(i+2,a,b,c,d,e),AC5(i+2,a,b,c,d,e))
#define CD5(i,a,b,c,d,e) IF(c,d,i,BD5(i+2,a,b,d,c,e),BD5(i+2,a,b,c,d,e))
#define DC5(i,a,b,c,d,e) IF(d,c,i, P5(i+2,a,b,c,d,e), P5(i+2,a,b,d,c,e))
#define DE5(i,a,b,c,d,e) IF(d,e,i,CB5(i+2,a,b,c,e,d),CB5(i+2,a,b,c,d,e))
#define P5(i,a,b,c,d,e) print_perm(i,5,(int[5]){a,b,c,d,e});
#define AB6(i,a,b,c,d,e,f) IF(a,b,i,CD6(i+2,b,a,c,d,e,f),CD6(i+2,a,b,c,d,e,f))
#define AC6(i,a,b,c,d,e,f) IF(a,c,i, P6(i+2,c,a,b,d,e,f), P6(i+2,a,c,b,d,e,f))
#define AE6(i,a,b,c,d,e,f) IF(a,e,i,CB6(i+2,e,a,c,b,d,f),CB6(i+2,a,e,c,b,d,f))
#define BD6(i,a,b,c,d,e,f) IF(b,d,i,DF6(i+2,c,d,a,b,e,f),DF6(i+2,a,b,c,d,e,f))
#define BE6(i,a,b,c,d,e,f) IF(b,e,i,AE6(i+2,a,b,c,d,e,f),DE6(i+2,a,b,c,d,e,f))
#define CB6(i,a,b,c,d,e,f) IF(c,b,i,DC6(i+2,a,b,c,d,e,f),AC6(i+2,a,b,c,d,e,f))
#define CD6(i,a,b,c,d,e,f) IF(c,d,i,EF6(i+2,a,b,d,c,e,f),EF6(i+2,a,b,c,d,e,f))
#define DB6(i,a,b,c,d,e,f) IF(d,b,i,BE6(i+2,a,b,c,d,e,f),BE6(i+2,c,d,a,b,e,f))
#define DC6(i,a,b,c,d,e,f) IF(d,c,i, P6(i+2,a,b,c,d,e,f), P6(i+2,a,b,d,c,e,f))
#define DE6(i,a,b,c,d,e,f) IF(d,e,i,CB6(i+2,a,b,c,e,d,f),CB6(i+2,a,b,c,d,e,f))
#define DF6(i,a,b,c,d,e,f) IF(d,f,i,DB6(i+2,a,b,e,f,c,d),BE6(i+2,a,b,c,d,e,f))
#define EF6(i,a,b,c,d,e,f) IF(e,f,i,BD6(i+2,a,b,c,d,f,e),BD6(i+2,a,b,c,d,e,f))
#define P6(i,a,b,c,d,e,f) print_perm(i,6,(int[6]){a,b,c,d,e,f});
#define SORT(ABn,n,...) \
OUT( 0, ""); \
OUT( 0, "inline void sort" #n "( int t[" #n "] ){" ) \
OUT( 2, "int tmp;" ) \
ABn( 2, __VA_ARGS__ ) \
OUT( 0, "}" )
void print_perm( int ind, int n, int t[n] ){
printf("%*.s", ind-1, "");
for( int i=0; i<n; i++ )
if( i != t[i] ){
printf(" tmp=t[%i]; t[%i]=",i,i);
for( int j=t[i],k; j!=i; k=j,j=t[j],t[k]=k)
printf("t[%i]; t[%i]=",j,j);
printf("tmp;");
}
printf("\n");
}
int main( void ){
SORT( AB2, 2, 0,1 )
SORT( AB3, 3, 0,1,2 )
SORT( AB4, 4, 0,1,2,3 )
SORT( AB5, 5, 0,1,2,3,4 )
SORT( AB6, 6, 0,1,2,3,4,5 )
}
El código generado 3718 líneas largas:
sort2(): 8 sort3(): 24 sort4(): 96 sort5(): 512 sort6(): 3072
Pruebe otro algoritmo de clasificación.
Dependiendo de sus datos, es posible que pueda intercambiar memoria por velocidad.
Según Wikipedia
- Ordenación rápida tiene un El mejor caso o (n log n) rendimiento y O (1) espacio
- Fusionar tiene un fijo o (n log n) rendimiento y En) espacio
- Radix Sort tiene un enfocado .u003Cnumber of digits> ) rendimiento y En .u003Cnumber of digits> ) espacio
Editar
Aparentemente, sus datos son enteros. Con 2.5m enteros en el rango [0, 0x0ffffff], mi implementación de Radix-Sort es aproximadamente 4 veces más rápida que su implementación de clases rápidas.
$ ./a.out qsort time: 0.39 secs radix time: 0.09 secs good: 2000; evil: 0
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define ARRAY_SIZE 2560000
#define RANDOM_NUMBER (((rand() << 16) + rand()) & 0x0fffffff)
int partition(int a[], int lower, int upper) {
int pivot, i, j, temp;
pivot = a[lower];
i = lower + 1;
j = upper;
while (i < j) {
while((i < upper) && (a[i] <= pivot)) i++;
while (a[j] > pivot) j--;
if (i < j) {
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
if (pivot > a[j]) {
temp = a[j];
a[j] = a[lower];
a[lower] = temp;
}
return j;
}
void quick(int a[], int lower, int upper) {
int loc;
if (lower < upper) {
loc = partition(a, lower, upper);
quick(a, lower, loc-1);
quick(a, loc+1, upper);
}
}
#define NBUCKETS 256
#define BUCKET_SIZE (48 * (1 + ARRAY_SIZE / NBUCKETS))
/* "waste" memory */
int bucket[NBUCKETS][BUCKET_SIZE];
void radix(int *a, size_t siz) {
unsigned shift = 0;
for (int dummy=0; dummy<4; dummy++) {
int bcount[NBUCKETS] = {0};
int *aa = a;
size_t s = siz;
while (s--) {
unsigned v = ((unsigned)*aa >> shift) & 0xff;
if (bcount[v] == BUCKET_SIZE) {
fprintf(stderr, "not enough memory.\n");
fprintf(stderr, "v == %u; bcount[v] = %d.\n", v, bcount[v]);
exit(EXIT_FAILURE);
}
bucket[v][bcount[v]++] = *aa++;
}
aa = a;
for (int k=0; k<NBUCKETS; k++) {
for (int j=0; j<bcount[k]; j++) *aa++ = bucket[k][j];
}
shift += 8;
}
}
int ar1[ARRAY_SIZE];
int ar2[ARRAY_SIZE];
int main(void) {
clock_t t0;
srand(time(0));
for (int k=0; k<ARRAY_SIZE; k++) ar1[k] = ar2[k] = RANDOM_NUMBER;
t0 = clock(); while (clock() == t0) /* void */; t0 = clock();
do {
quick(ar1, 0, ARRAY_SIZE - 1);
} while (0);
double qsort_time = (double)(clock() - t0) / CLOCKS_PER_SEC;
t0 = clock(); while (clock() == t0) /* void */; t0 = clock();
do {
radix(ar2, ARRAY_SIZE);
} while (0);
double radix_time = (double)(clock() - t0) / CLOCKS_PER_SEC;
printf("qsort time: %.2f secs\n", qsort_time);
printf("radix time: %.2f secs\n", radix_time);
/* compare sorted arrays by sampling */
int evil = 0;
int good = 0;
for (int chk=0; chk<2000; chk++) {
size_t index = RANDOM_NUMBER % ARRAY_SIZE;
if (ar1[index] == ar2[index]) good++;
else evil++;
}
printf("good: %d; evil: %d\n", good, evil);
return 0;
}
los Artículo de Wikipedia sobre Quicksort tiene un montón de ideas.
Puede eliminar la sobrecarga de recuriosn utilizando QuickSort con una pila explícita
void quickSort(int a[], int lower, int upper) { createStack(); push(lower); push(upper); while (!isEmptyStack()) { upper=poptop(); lower=poptop(); while (lower<upper) { pivPos=partition(selectPivot(a, size), a, lower, upper); push(lower); push(pivPos-1); lower = pivPos+1; // end = end; } } }Puede usar una mejor técnica de selección de pivote como:
- mediana de 3
- mediana de medianas
- pivote al azar
Actualmente, el QuickSort más avanzado ampliamente utilizado se implementa en Java's Dualpivotquicksort.javaEntonces, simplemente puede seguir ese enfoque y verá una buena mejora del rendimiento:
- Use el orden de inserción para matrices pequeñas (47 es el número utilizado en Java)
- Use ese rápido pivote de doble pivote eligiendo los elementos segundo y cuarto de 5 como los dos pivotes
- Considere usar Mergesort para matrices con ejecuciones de números ordenados
O si desea agregar un poco más de complejidad, codifique un 3 pivote rápido.
Si esto no es solo para el uso de aprendizaje QSORT de stdlib.h
Según su código, cuando se clasifica Lenght es de 10, se ve la pila más profunda
#0 partition (a=0x7fff5ac42180, lower=3, upper=5)
#1 0x000000000040062f in quick (a=0x7fff5ac42180, lower=3, upper=5)
#2 0x0000000000400656 in quick (a=0x7fff5ac42180, lower=0, upper=5)
#3 0x0000000000400644 in quick (a=0x7fff5ac42180, lower=0, upper=8)
#4 0x0000000000400644 in quick (a=0x7fff5ac42180, lower=0, upper=9)
#5 0x00000000004005c3 in main
Además del algo en sí, si consideramos el comportamiento del sistema, como las actividades de la pila, algo más, excepto los costos normales de la pila de llamadas (push/pop) podría degradar el rendimiento mucho, por ejemplo, el cambio de contexto si el sistema de tareas múltiples, ya conoce la mayoría del sistema operativo son multitarea, y más profundamente la pila más alta costaba la conmutación, además de la fallas de caché o el límite de caché.
Creo en este caso si la longitud se hace más grande, perderá al compararse con otros algos de clasificación.
Por ejemplo, cuando la longitud es de hasta 40, la pila puede parecer (puede más entradas que las que se muestran a continuación):
#0 partition (a=0x7fff24810cd0, lower=8, upper=9)
#1 0x000000000040065d in quick (a=0x7fff24810cd0, lower=8, upper=9)
#2 0x0000000000400672 in quick (a=0x7fff24810cd0, lower=8, upper=10)
#3 0x0000000000400672 in quick (a=0x7fff24810cd0, lower=8, upper=14)
#4 0x0000000000400684 in quick (a=0x7fff24810cd0, lower=4, upper=14)
#5 0x0000000000400672 in quick (a=0x7fff24810cd0, lower=4, upper=18)
#6 0x0000000000400684 in quick (a=0x7fff24810cd0, lower=0, upper=18)
#7 0x0000000000400672 in quick (a=0x7fff24810cd0, lower=0, upper=26)
#8 0x0000000000400672 in quick (a=0x7fff24810cd0, lower=0, upper=38)
#9 0x0000000000400672 in quick (a=0x7fff24810cd0, lower=0, upper=39)
#10 0x00000000004005ee in main
Demasiado más profundo de la pila.
La función de la función también es útil, pero aumenta la huella del código del ejecutable final. Estoy de acuerdo con @Swiss, la programación paralela podría ayudarte mucho.
Respuesta completamente tonta, pero ... ¡compile su código en modo de lanzamiento y active las optimizaciones!
Lo primero que debe hacer es compararlo. Y compararlo con el QSort estándar, y contra el C ++ std :: sort y std :: stable_sort.
Sus resultados, si su conjunto de datos es lo suficientemente grande, mostrará que el std :: sort es superior a Qsort en todos los casos excepto aquellos donde el std :: stable_sort es superior. Esto se debe a que el std :: sort se plantilla y, por lo tanto, la comparación puede enlleva.
Su código introduce la comparación porque no es genérico. Si su código es más lento que QSORT, tiene un problema allí mismo.
El tipo más rápido sería clasificar las partes en paralelo, por ejemplo, OpenMP, y luego fusionarlas de nuevo.
Copié de mi respuesta para responder la pregunta.
Editar: Esta publicación supone que ya hace cosas obvias como aprovechar la recursión de la cola para deshacerse de la llamada innecesaria.
A la gente le gusta criticar el rápido rendimiento con ciertos aportes, especialmente Cuando el usuario tiene control de la entrada. El siguiente enfoque produce la selección de punto medio que coincide con el rendimiento, pero la complejidad esperada exponencialmente enfoques o (norte Iniciar sesión norte) a medida que la lista crece en tamaño. En mi experiencia, supera significativamente la mejor selección de 3 debido a mucho menos gastos generales en el caso mayoritario. Debe funcionar uniformemente con la selección de punto medio para las entradas "esperadas", pero no es vulnerable a las malas entradas.
- Inicializar el QuickSort con un entero positivo aleatorio
I. Ese valor se utilizará a lo largo del proceso de clasificación (no tiene que generar múltiples números). - Pivot se selecciona como
I mod SectionSize.
Para un rendimiento adicional, siempre debe cambiar su clasificación de Shell a Shell para segmentos de lista "pequeños": he visto longitudes de 15 a 100 elegidas como el límite.
¿Múltiple lectura?
/*
* multiple-thread quick-sort.
* Works fine on uniprocessor machines as well.
*/
#include <unistd.h>
#include <stdlib.h>
#include <thread.h>
/* don't create more threads for less than this */
#define SLICE_THRESH 4096
/* how many threads per lwp */
#define THR_PER_LWP 4
/* cast the void to a one byte quanitity and compute the offset */
#define SUB(a, n) ((void *) (((unsigned char *) (a)) + ((n) * width)))
typedef struct {
void *sa_base;
int sa_nel;
size_t sa_width;
int (*sa_compar)(const void *, const void *);
} sort_args_t;
/* for all instances of quicksort */
static int threads_avail;
#define SWAP(a, i, j, width)
{
int n;
unsigned char uc;
unsigned short us;
unsigned long ul;
unsigned long long ull;
if (SUB(a, i) == pivot)
pivot = SUB(a, j);
else if (SUB(a, j) == pivot)
pivot = SUB(a, i);
/* one of the more convoluted swaps I've done */
switch(width) {
case 1:
uc = *((unsigned char *) SUB(a, i));
*((unsigned char *) SUB(a, i)) = *((unsigned char *) SUB(a, j));
*((unsigned char *) SUB(a, j)) = uc;
break;
case 2:
us = *((unsigned short *) SUB(a, i));
*((unsigned short *) SUB(a, i)) = *((unsigned short *) SUB(a, j));
*((unsigned short *) SUB(a, j)) = us;
break;
case 4:
ul = *((unsigned long *) SUB(a, i));
*((unsigned long *) SUB(a, i)) = *((unsigned long *) SUB(a, j));
*((unsigned long *) SUB(a, j)) = ul;
break;
case 8:
ull = *((unsigned long long *) SUB(a, i));
*((unsigned long long *) SUB(a,i)) = *((unsigned long long *) SUB(a,j));
*((unsigned long long *) SUB(a, j)) = ull;
break;
default:
for(n=0; n<width; n++) {
uc = ((unsigned char *) SUB(a, i))[n];
((unsigned char *) SUB(a, i))[n] = ((unsigned char *) SUB(a, j))[n];
((unsigned char *) SUB(a, j))[n] = uc;
}
break;
}
}
static void *
_quicksort(void *arg)
{
sort_args_t *sargs = (sort_args_t *) arg;
register void *a = sargs->sa_base;
int n = sargs->sa_nel;
int width = sargs->sa_width;
int (*compar)(const void *, const void *) = sargs->sa_compar;
register int i;
register int j;
int z;
int thread_count = 0;
void *t;
void *b[3];
void *pivot = 0;
sort_args_t sort_args[2];
thread_t tid;
/* find the pivot point */
switch(n) {
case 0:
case 1:
return 0;
case 2:
if ((*compar)(SUB(a, 0), SUB(a, 1)) > 0) {
SWAP(a, 0, 1, width);
}
return 0;
case 3:
/* three sort */
if ((*compar)(SUB(a, 0), SUB(a, 1)) > 0) {
SWAP(a, 0, 1, width);
}
/* the first two are now ordered, now order the second two */
if ((*compar)(SUB(a, 2), SUB(a, 1)) < 0) {
SWAP(a, 2, 1, width);
}
/* should the second be moved to the first? */
if ((*compar)(SUB(a, 1), SUB(a, 0)) < 0) {
SWAP(a, 1, 0, width);
}
return 0;
default:
if (n > 3) {
b[0] = SUB(a, 0);
b[1] = SUB(a, n / 2);
b[2] = SUB(a, n - 1);
/* three sort */
if ((*compar)(b[0], b[1]) > 0) {
t = b[0];
b[0] = b[1];
b[1] = t;
}
/* the first two are now ordered, now order the second two */
if ((*compar)(b[2], b[1]) < 0) {
t = b[1];
b[1] = b[2];
b[2] = t;
}
/* should the second be moved to the first? */
if ((*compar)(b[1], b[0]) < 0) {
t = b[0];
b[0] = b[1];
b[1] = t;
}
if ((*compar)(b[0], b[2]) != 0)
if ((*compar)(b[0], b[1]) < 0)
pivot = b[1];
else
pivot = b[2];
}
break;
}
if (pivot == 0)
for(i=1; i<n; i++) {
if (z = (*compar)(SUB(a, 0), SUB(a, i))) {
pivot = (z > 0) ? SUB(a, 0) : SUB(a, i);
break;
}
}
if (pivot == 0)
return;
/* sort */
i = 0;
j = n - 1;
while(i <= j) {
while((*compar)(SUB(a, i), pivot) < 0)
++i;
while((*compar)(SUB(a, j), pivot) >= 0)
--j;
if (i < j) {
SWAP(a, i, j, width);
++i;
--j;
}
}
/* sort the sides judiciously */
switch(i) {
case 0:
case 1:
break;
case 2:
if ((*compar)(SUB(a, 0), SUB(a, 1)) > 0) {
SWAP(a, 0, 1, width);
}
break;
case 3:
/* three sort */
if ((*compar)(SUB(a, 0), SUB(a, 1)) > 0) {
SWAP(a, 0, 1, width);
}
/* the first two are now ordered, now order the second two */
if ((*compar)(SUB(a, 2), SUB(a, 1)) < 0) {
SWAP(a, 2, 1, width);
}
/* should the second be moved to the first? */
if ((*compar)(SUB(a, 1), SUB(a, 0)) < 0) {
SWAP(a, 1, 0, width);
}
break;
default:
sort_args[0].sa_base = a;
sort_args[0].sa_nel = i;
sort_args[0].sa_width = width;
sort_args[0].sa_compar = compar;
if ((threads_avail > 0) && (i > SLICE_THRESH)) {
threads_avail--;
thr_create(0, 0, _quicksort, &sort_args[0], 0, &tid);
thread_count = 1;
} else
_quicksort(&sort_args[0]);
break;
}
j = n - i;
switch(j) {
case 1:
break;
case 2:
if ((*compar)(SUB(a, i), SUB(a, i + 1)) > 0) {
SWAP(a, i, i + 1, width);
}
break;
case 3:
/* three sort */
if ((*compar)(SUB(a, i), SUB(a, i + 1)) > 0) {
SWAP(a, i, i + 1, width);
}
/* the first two are now ordered, now order the second two */
if ((*compar)(SUB(a, i + 2), SUB(a, i + 1)) < 0) {
SWAP(a, i + 2, i + 1, width);
}
/* should the second be moved to the first? */
if ((*compar)(SUB(a, i + 1), SUB(a, i)) < 0) {
SWAP(a, i + 1, i, width);
}
break;
default:
sort_args[1].sa_base = SUB(a, i);
sort_args[1].sa_nel = j;
sort_args[1].sa_width = width;
sort_args[1].sa_compar = compar;
if ((thread_count == 0) && (threads_avail > 0) && (i > SLICE_THRESH)) {
threads_avail--;
thr_create(0, 0, _quicksort, &sort_args[1], 0, &tid);
thread_count = 1;
} else
_quicksort(&sort_args[1]);
break;
}
if (thread_count) {
thr_join(tid, 0, 0);
threads_avail++;
}
return 0;
}
void
quicksort(void *a, size_t n, size_t width,
int (*compar)(const void *, const void *))
{
static int ncpus = -1;
sort_args_t sort_args;
if (ncpus == -1) {
ncpus = sysconf( _SC_NPROCESSORS_ONLN);
/* lwp for each cpu */
if ((ncpus > 1) && (thr_getconcurrency() < ncpus))
thr_setconcurrency(ncpus);
/* thread count not to exceed THR_PER_LWP per lwp */
threads_avail = (ncpus == 1) ? 0 : (ncpus * THR_PER_LWP);
}
sort_args.sa_base = a;
sort_args.sa_nel = n;
sort_args.sa_width = width;
sort_args.sa_compar = compar;
(void) _quicksort(&sort_args);
}
