sort explicado código codigo c++ algorithm sorting quicksort

c++ - explicado - ¿Alguien ha visto esta mejora a quicksort antes?



quicksort c++ codigo (5)

Es una gran mejora y estoy seguro de que se ha implementado específicamente si espera muchos objetos iguales. Hay muchos de los tweeks de pared de este tipo.

Si entiendo todo lo que escribiste correctamente, la razón por la que generalmente no es "conocido" es que mejora el rendimiento básico de O (n2). Eso significa, duplicar el número de objetos, cuadruplicar el tiempo. Tu mejora no cambia esto a menos que todos los objetos sean iguales.

Manejo de elementos repetidos en quicksorts anteriores.

He encontrado una manera de manejar los elementos repetidos de manera más eficiente en Quicksort y me gustaría saber si alguien ha visto esto antes.

Este método reduce en gran medida la sobrecarga involucrada en la comprobación de elementos repetidos, lo que mejora el rendimiento con y sin elementos repetidos. Por lo general, los elementos repetidos se manejan de varias maneras diferentes que primero enumeraré.

Primero, está el método de la bandera nacional holandesa que clasifica la matriz como [ < pivot | == pivot | unsorted | > pivot] [ < pivot | == pivot | unsorted | > pivot] [ < pivot | == pivot | unsorted | > pivot] .

Segundo, existe el método de colocar los elementos iguales en el extremo izquierdo durante la clasificación y luego moverlos al centro, la clasificación es [ == pivot | < pivot | unsorted | > pivot] [ == pivot | < pivot | unsorted | > pivot] [ == pivot | < pivot | unsorted | > pivot] y luego, después del ordenamiento, los elementos == se mueven al centro.

En tercer lugar, la partición Bentley-McIlroy coloca los elementos == a ambos lados, por lo que la clasificación es [ == pivot | < pivot | unsorted | > pivot | == pivot] [ == pivot | < pivot | unsorted | > pivot | == pivot] [ == pivot | < pivot | unsorted | > pivot | == pivot] y luego los elementos == se mueven al medio.

Los dos últimos métodos se realizan en un intento de reducir la sobrecarga.

Mi metodo

Ahora, permítanme explicar cómo mi método mejora la ordenación rápida al reducir el número de comparaciones. Utilizo dos funciones de orden rápido juntas en lugar de una sola.

La primera función la llamaré q1 y ordena una matriz como [ < pivot | unsorted | >= pivot] [ < pivot | unsorted | >= pivot] [ < pivot | unsorted | >= pivot] .

La segunda función la llamaré q2 y ordena la matriz como [ <= pivot | unsorted | > pivot] [ <= pivot | unsorted | > pivot] [ <= pivot | unsorted | > pivot] .

Veamos ahora el uso de estos en tándem para mejorar el manejo de elementos repetidos.

En primer lugar, llamamos q1 para ordenar toda la matriz. Escoge un pivote al que haremos referencia adicional como pivot1 y luego clasificamos alrededor de pivot1 . Por lo tanto, nuestra matriz está ordenada hasta este punto como [ < pivot1 | >= pivot1 ] [ < pivot1 | >= pivot1 ] .

Luego, para la partición [ < pivot1] , lo enviamos nuevamente a q1 , y esa parte es bastante normal, así que primero [ < pivot1] la otra partición.

Para la partición [ >= pivot1] , lo enviamos a q2 . q2 elige un pivote, al que haremos referencia como pivot2 desde dentro de esta sub-matriz y lo clasifica en [ <= pivot2 | > pivot2] [ <= pivot2 | > pivot2] .

Si nos fijamos ahora en toda la matriz, nuestra clasificación se ve como [ < pivot1 | >= pivot1 and <= pivot2 | > pivot2] [ < pivot1 | >= pivot1 and <= pivot2 | > pivot2] [ < pivot1 | >= pivot1 and <= pivot2 | > pivot2] . Esto se parece mucho a un quicksort de doble pivote.

Ahora, volvamos al subarreglo dentro de q2 ( [ <= pivot2 | > pivot2] ).

Para la partición [ > pivot2] , simplemente lo enviamos de vuelta a q1 que no es muy interesante.

Para la partición [ <= pivot2] , primero verificamos si pivot1 == pivot2 . Si son iguales, entonces esta partición ya está ordenada porque todos son elementos iguales. Si los pivotes no son iguales, entonces simplemente enviamos esta partición a q2 nuevamente, que elige un pivote (más pivot3 ), ordena, y si pivot3 == pivot1 , entonces no tiene que ordenar el [ <= pivot 3] y pronto.

Con suerte, ya entiendes el punto. La mejora con esta técnica es que los elementos iguales se manejan sin tener que verificar si cada elemento también es igual a los pivotes. En otras palabras, utiliza menos comparaciones.

Hay otra posible mejora que aún no he probado, que es comprobar en qs2 si el tamaño de la partición [ <= pivot2] es bastante grande (o la partición [> pivot2] es muy pequeña) en comparación con el tamaño de su subarreglo total y luego realizar una verificación más estándar de elementos repetidos en ese caso (uno de los métodos mencionados anteriormente).

Código fuente

Aquí hay dos funciones qs1 y qs2 muy simplificadas. Utilizan el método de clasificación de punteros convergentes de Sedgewick. Obviamente, pueden estar muy optimizados (por ejemplo, eligen los pivotes de manera muy pobre), pero esto es solo para mostrar la idea. Mi propia implementación es más larga, más rápida y mucho más difícil de leer, así que comencemos con esto:

// qs sorts into [ < p | >= p ] void qs1(int a[], long left, long right){ // Pick a pivot and set up some indicies int pivot = a[right], temp; long i = left - 1, j = right; // do the sort for(;;){ while(a[++i] < pivot); while(a[--j] >= pivot) if(i == j) break; if(i >= j) break; temp = a[i]; a[i] = a[j]; a[j] = temp; } // Put the pivot in the correct spot temp = a[i]; a[i] = a[right]; a[right] = temp; // send the [ < p ] partition to qs1 if(left < i - 1) qs1(a, left, i - 1); // send the [ >= p] partition to qs2 if( right > i + 1) qs2(a, i + 1, right); } void qs2(int a[], long left, long right){ // Pick a pivot and set up some indicies int pivot = a[left], temp; long i = left, j = right + 1; // do the sort for(;;){ while(a[--j] > pivot); while(a[++i] <= pivot) if(i == j) break; if(i >= j) break; temp = a[i]; a[i] = a[j]; a[j] = temp; } // Put the pivot in the correct spot temp = a[j]; a[j] = a[left]; a[left] = temp; // Send the [ > p ] partition to qs1 if( right > j + 1) qs1(a, j + 1, right); // Here is where we check the pivots. // a[left-1] is the other pivot we need to compare with. // This handles the repeated elements. if(pivot != a[left-1]) // since the pivots don''t match, we pass [ <= p ] on to qs2 if(left < j - 1) qs2(a, left, j - 1); }

Sé que esta es una idea bastante simple, pero brinda una mejora bastante significativa en el tiempo de ejecución cuando agrego las mejoras estándar de clase rápida (selección de pivote de mediana de 3 y ordenación por inserción para una matriz pequeña para comenzar). Si va a probar utilizando este código, solo hágalo en datos aleatorios debido a la mala elección del pivote (o mejore la elección del pivote). Para utilizar este tipo llamaría:

qs1(array,0,indexofendofarray);

Algunos puntos de referencia

Si desea saber qué tan rápido es, aquí hay algunos datos para empezar. Esto usa mi versión optimizada, no la dada arriba. Sin embargo, el que se da más arriba todavía está mucho más cerca en el tiempo del quicksort de doble pivote que el std::sort time.

En datos altamente aleatorios con 2,000,000 elementos, obtengo estos tiempos (de la clasificación de varios conjuntos de datos consecutivos):

std::sort - 1.609 seconds dual-pivot quicksort - 1.25 seconds qs1/qs2 - 1.172 seconds

Donde std::sort es la std::sort la biblioteca estándar de C ++, el quicksort de doble pivote es el que salió hace varios meses por Vladimir Yaroslavskiy, y qs1/qs2 es mi implementación de quicksort.

En datos mucho menos aleatorios. con 2,000,000 elementos y generado con rand() % 1000 (lo que significa que cada elemento tiene aproximadamente 2000 copias) los tiempos son:

std::sort - 0.468 seconds dual-pivot quicksort - 0.438 seconds qs1/qs2 - 0.407 seconds

Hay algunos casos en los que el quicksort de doble pivote gana y me doy cuenta de que el quicksort de doble pivote podría optimizarse más, pero lo mismo podría establecerse de forma segura para mi quicksort.

¿Alguien ha visto esto antes?

Sé que esta es una pregunta / explicación larga, pero ¿alguno de ustedes ha visto esta mejora antes? Si es así, ¿por qué no se está utilizando?

Para responder a su pregunta, no, no he visto este enfoque antes. No voy a perfilar su código y hacer el otro trabajo duro, pero quizás los siguientes son los siguientes pasos / consideraciones para presentar formalmente su algoritmo. En el mundo real, los algoritmos de clasificación se implementan para tener:

Buena escalabilidad / complejidad y baja sobrecarga

La escala y la sobrecarga son obvias y son fáciles de medir. Al perfilar la clasificación, además del tiempo, medir el número de comparaciones y swaps. El rendimiento en archivos grandes también dependerá del tiempo de búsqueda del disco. Por ejemplo, la ordenación de combinación funciona bien en archivos grandes con un disco magnético. (vea también Ordenamiento rápido Vs Combinar ordenamiento )

Amplia gama de entradas con buen rendimiento.

Hay muchos datos que necesitan ordenación. Y se sabe que las aplicaciones producen datos en patrones, por lo que es importante hacer que la clasificación sea resistente frente al bajo rendimiento bajo ciertos patrones. Su algoritmo se optimiza para los números repetidos. ¿Qué pasa si todos los números se repiten pero solo una vez (es decir, seq 1000> archivo; seq 1000 >> archivo; archivo shuf)? ¿Qué pasa si los números ya están ordenados? ordenado al revés? ¿Qué pasa con un patrón de 1,2,3,1,2,3,1,2,3,1,2,3? 1,2,3,4,5,6,7,6,5,4,3,2,1? 7,6,5,4,3,2,1,2,3,4,5,6,7? ¡El bajo rendimiento en uno de estos escenarios comunes es un factor decisivo! Antes de compararlo con un algoritmo de propósito general publicado, es aconsejable tener este análisis preparado.

Bajo riesgo de comportamiento patológico.

De todas las permutaciones de las entradas, hay una que se comporta peor que las otras. ¿Cuánto peor es el rendimiento que el promedio? ¿Y cuántas permutaciones proporcionarán un rendimiento pobre similar?

¡Buena suerte en tus próximos pasos!

Parece que a nadie le gusta tu algoritmo, pero a mí sí. Me parece que es una buena forma de volver a hacer el clasico quicksort de una manera ahora segura para usar con elementos altamente repetidos. Tus subalgorithms q1 y q2, me parece que son el MISMO algoritmo, excepto que los operadores <y <= se intercambiaron y algunas otras cosas, que si quisieras te permitirían escribir un pseudocódigo más corto para esto (aunque podría ser menos eficiente). Recomendamos que lea JL Bentley, MD McIlroy: Diseñando una función de clasificación
SOFTWARE: PRÁCTICA Y EXPERIENCIA 23,11 (noviembre de 1993) 1249-1265 e-disponible aquí http://www.skidmore.edu/~meckmann/2009Spring/cs206/papers/spe862jb.pdf para ver las pruebas a las que someten su ordenamiento rápido . Su idea podría ser mejor y / o mejor, pero necesita ejecutar el guante de los tipos de pruebas que probaron, utilizando algún método particular de elección de pivote. Encuentra uno que supere todas sus pruebas sin sufrir nunca un tiempo de ejecución cuadrático. Entonces, si además su algoritmo es más rápido y más agradable que el de ellos, claramente tendrá una contribución valiosa.

El "Tukey Ninther" que ellos usan para generar un pivote me parece que también es utilizable y automáticamente hará que sea muy difícil que el peor momento cuadrático surja en la práctica. Quiero decir, si solo usas la mediana de 3 e intentas los elementos medio y dos extremos de la matriz como tus tres, entonces un adversario hará que el estado de la matriz inicial aumente y luego disminuya, y luego caerás de bruces con Tiempo de ejecución cuadrático en una entrada no demasiado inverosímil. Pero con Tukey Ninther en 9 elementos, es bastante difícil para mí construir una entrada plausible que te haga daño con el tiempo de ejecución cuadrático.

Otra vista y una sugerencia: piense en la combinación de q1 dividiendo su matriz, luego q2 dividiendo la subarreglo correcto, como un solo algoritmo q12 que produce una división de 3 vías de la matriz. Ahora, necesita recursionar en los 3 subarreglos (o solo 2 si los dos pivotes son iguales). Ahora recuerde siempre el PRIMER más pequeño de los subgrupos que iba a realizar, PRIMERO, y el ÚLTIMO más grande, y no implemente este más grande como una recursión, sino que permanezca en la misma rutina y vuelva hasta la parte superior. Con una ventana encogida. De esa manera, tiene 1 llamada recursiva menos en q12 de la que tendría, pero el punto principal de esto es que ahora es IMPOSIBLE que la pila de recursión tenga más de O (logN). ¿OKAY? Esto resuelve otro problema molesto en el peor de los casos que Quicksort puede sufrir al mismo tiempo que también hace que su código sea un poco más rápido.

std: ordenar no es exactamente rápido.

Aquí están los resultados que obtengo al compararlo con el orden aleatorio no recursivo paralelo aleatorio:

pnrqSort (longs):.:. 1 000 000 36ms (elementos por ms: 27777.8)

.:. 5 000 000 140ms (elementos por ms: 35714.3)

.:. 10 000 000 296ms (elementos por ms: 33783.8)

.:. 50 000 000 1s 484ms (elementos por ms: 33692.7)

.:. 100 000 000 2s 936ms (elementos por ms: 34059.9)

.:. 250 000 000 8s 300ms (elementos por ms: 30120.5)

.:. 400 000 000 12s 611ms (elementos por ms: 31718.3)

.:. 500 000 000 16s 428ms (elementos por ms: 30435.8)

std :: sort (longs).:. 1 000 000 134ms (elementos por ms: 7462.69)

.:. 5 000 000 716ms (elementos por ms: 6983.24)

std :: vector de clasificación de los largos

1 000 000 511 ms (elementos por ms: 1956.95)

2 500 000 943ms (elementos por ms: 2651.11)

Ya que tiene un método adicional, causará más uso de pila, lo que en última instancia ralentizará las cosas. No sé por qué se utiliza la mediana de 3, porque es un método deficiente, pero con puntos de pivote aleatorios, Quicksort nunca tiene grandes problemas con datos uniformes o preclasificados y no hay peligro de que la mediana intencional de 3 datos asesinos.