c++ - ordenar - elementos de cola de prioridades

¿Qué es más rápido: insertarlo en una cola de prioridad o ordenar retrospectivamente?

Question

¿Qué es más rápido: insertarlo en una cola de prioridad o ordenar retrospectivamente?

Estoy generando algunos elementos que necesito para ser ordenados al final. Me preguntaba, ¿qué es más rápido en términos de complejidad: insertarlos directamente en una prioridad o en una estructura de datos similar, o usar un algoritmo de clasificación al final?

Answer 1

¿Por qué no usar un árbol de búsqueda binario? Luego, los elementos se ordenan en todo momento y los costos de inserción son iguales a la cola de prioridad. Lea acerca de los árboles equilibrados RedBlack here

Answer 2

A tu primera pregunta (que es más rápida): depende. Sólo pruébalo. Suponiendo que desee el resultado final en un vector, las alternativas podrían tener este aspecto:

#include <iostream>
#include <vector>
#include <queue>
#include <cstdlib>
#include <functional>
#include <algorithm>
#include <iterator>
#ifndef NUM
#define NUM 10
#endif
int main() {
std::srand(1038749);
std::vector<int> res;
#ifdef USE_VECTOR
for (int i = 0; i < NUM; ++i) {
res.push_back(std::rand());
}
std::sort(res.begin(), res.end(), std::greater<int>());
#else
std::priority_queue<int> q;
for (int i = 0; i < NUM; ++i) {
q.push(std::rand());
}
res.resize(q.size());
for (int i = 0; i < NUM; ++i) {
res[i] = q.top();
q.pop();
}
#endif
#if NUM <= 10
std::copy(res.begin(), res.end(), std::ostream_iterator<int>(std::cout,"/n"));
#endif
}
$ g++ sortspeed.cpp -o sortspeed -DNUM=10000000 && time ./sortspeed
real 0m20.719s
user 0m20.561s
sys 0m0.077s
$ g++ sortspeed.cpp -o sortspeed -DUSE_VECTOR -DNUM=10000000 && time ./sortspeed
real 0m5.828s
user 0m5.733s
sys 0m0.108s

Entonces, std::sort beats std::priority_queue , en este caso . Pero quizás tenga una mejor o peor std:sort , y tal vez tenga una mejor o peor implementación de un montón. O si no es mejor o peor, más o menos adecuado para su uso exacto, que es diferente de mi uso inventado: "crear un vector ordenado que contenga los valores".

Puedo decir con mucha confianza que los datos aleatorios no afectarán al peor de los casos de std::sort , por lo que, en un sentido, esta prueba podría aplacarlo. Pero para una buena implementación de std::sort , su peor caso será muy difícil de construir y, de hecho, podría no ser tan malo.

Edición: Agregué el uso de un conjunto múltiple, ya que algunas personas han sugerido un árbol:

 #elif defined(USE_SET)
std::multiset<int,std::greater<int> > s;
for (int i = 0; i < NUM; ++i) {
s.insert(std::rand());
}
res.resize(s.size());
int j = 0;
for (std::multiset<int>::iterator i = s.begin(); i != s.end(); ++i, ++j) {
res[j] = *i;
}
#else
$ g++ sortspeed.cpp -o sortspeed -DUSE_SET -DNUM=10000000 && time ./sortspeed
real 0m26.656s
user 0m26.530s
sys 0m0.062s

A la segunda pregunta (complejidad): todos son O (n log n), ignorando los detalles de implementación complicados, como si la asignación de memoria es O (1) o no ( vector::push_back y otras formas de inserción al final se amortizan O (1)) y suponiendo que por "ordenación" se entiende una ordenación de comparación. Otros tipos de clase pueden tener menor complejidad.

Answer 3

Creo que la inserción es más eficiente en casi todos los casos en los que está generando los datos (es decir, no los tiene en una lista).

Una cola de prioridad no es su única opción de inserción a medida que avanza. Como se mencionó en otras respuestas, un árbol binario (o un árbol RB relacionado) es igualmente eficiente.

También verificaría cómo se implementa la cola de prioridad: muchas ya se basan en b-trees, pero algunas implementaciones no son muy buenas para extraer los elementos (esencialmente pasan por toda la cola y buscan la prioridad más alta).

Answer 4

Depende de los datos, pero generalmente creo que InsertSort es más rápido.

Tenía una pregunta relacionada, y al final descubrí que el cuello de botella era simplemente que estaba haciendo una especie de aplazamiento (solo cuando lo necesitaba) y en una gran cantidad de artículos, generalmente tenía el peor de los casos para mi QuickSort (ya en orden), así que usé un orden de inserción

Ordenando 1000-2000 elementos con muchos fallos de caché

¡Así que analiza tus datos!

Answer 5

En una cola de prioridad de inserción máxima, las operaciones son O (lg n)

Answer 6

Por lo que entiendo, su problema no requiere una cola de prioridad, ya que sus tareas suenan como "Haga muchas inserciones, después de eso ordene todo". Es como disparar a los pájaros con un láser, no una herramienta adecuada. Utilice técnicas de clasificación estándar para eso.

Necesitaría una cola de prioridad, si su tarea fuera imitar una secuencia de operaciones, donde cada operación puede ser "Agregar un elemento al conjunto" o "Eliminar el elemento más grande / más grande del conjunto". Esto se puede usar en el problema de encontrar una ruta más corta en el gráfico, por ejemplo. Aquí no puedes usar técnicas de clasificación estándar.

Answer 7

Probablemente esto te llegue un poco tarde en el juego en lo que respecta a tu pregunta, pero seamos completos.

Las pruebas son la mejor manera de responder esta pregunta para la arquitectura, el compilador y la implementación específicos de su computadora. Más allá de eso, hay generalizaciones.

En primer lugar, las colas de prioridad no son necesariamente O (n log n).

Si tiene datos enteros, hay colas de prioridad que funcionan en tiempo O (1). La publicación de 1992 de Beucher y Meyer "El enfoque morfológico de la segmentación: la transformación de la cuenca hidrográfica" describe colas jerárquicas, que funcionan con bastante rapidez para valores enteros con rango limitado. La publicación de Brown en 1988 "Las colas del calendario: una rápida implementación de la cola de prioridad 0 (1) para el problema del conjunto de eventos de simulación" ofrece otra solución que se adapta bien a rangos más grandes de enteros: dos décadas de trabajo después de la publicación de Brown ha producido algunos buenos resultados al hacer enteros Las colas de prioridad son rápidas . Sin embargo, la maquinaria de estas colas puede complicarse: los tipos de cubeta y de tipo radix todavía pueden proporcionar una operación O (1). En algunos casos, es posible que incluso pueda cuantificar datos de punto flotante para aprovechar una cola de prioridad O (1).

Incluso en el caso general de los datos de punto flotante, esa O (n log n) es un poco engañosa. El libro de Edelkamp "Búsqueda heurística: teoría y aplicaciones" tiene la siguiente tabla práctica que muestra la complejidad del tiempo para varios algoritmos de colas de prioridad (recuerde, las colas de prioridad son equivalentes a la ordenación y la administración del montón):

Como puede ver, muchas colas de prioridad tienen costos O (log n) no solo para la inserción, sino también para la extracción, ¡e incluso para la administración de colas! Si bien el coeficiente generalmente se reduce para medir la complejidad del tiempo de un algoritmo, estos costos aún son dignos de conocer.

Pero todas estas colas todavía tienen complejidades de tiempo que son comparables. ¿Cuál es el mejor? Un documento de 2010 de Cris L. Luengo Hendriks titulado "Revisar las colas de prioridad para el análisis de imágenes" aborda esta pregunta.

En la prueba de retención de Hendriks, se sembró una cola de prioridad con N números aleatorios en el rango [0,50] . El elemento más superior de la cola se eliminó en cola, se incrementó en un valor aleatorio en el rango [0,2] y luego se colocó en cola. Esta operación se repitió 10 ^ 7 veces. La sobrecarga de generar los números aleatorios se restó de los tiempos medidos. Las colas de escalera y los montones jerárquicos se realizaron bastante bien con esta prueba.

También se midió el tiempo por elemento para inicializar y vaciar las colas, estas pruebas son muy relevantes para su pregunta.

Como puede ver, las diferentes colas a menudo tenían respuestas muy diferentes al encolado y al encolado. Estas cifras implican que, si bien puede haber algoritmos de cola de prioridad que son superiores para la operación continua, no hay una mejor opción de algoritmo para simplemente rellenar y luego vaciar una cola de prioridad (la operación que está haciendo).

Echemos un vistazo atrás a sus preguntas:

¿Qué es más rápido: insertarlo en una cola de prioridad o ordenar retrospectivamente?

Como se muestra arriba, las colas de prioridad pueden hacerse eficientes, pero aún existen costos de inserción, eliminación y administración. La inserción en un vector es rápida. Es O (1) en tiempo amortizado, y no hay costos de administración, más el vector es O (n) para ser leído.

Ordenar el vector le costará O (n log n) suponiendo que tiene datos de punto flotante, pero esta vez la complejidad no oculta cosas como las colas de prioridad. (Sin embargo, debe tener un poco de cuidado. Quicksort funciona muy bien con algunos datos, pero tiene una complejidad en el peor de los casos de O (n ^ 2). Para algunas implementaciones, esto es un riesgo de seguridad grave).

Me temo que no tengo datos sobre los costos de clasificación, pero diría que la clasificación retroactiva captura la esencia de lo que se está tratando de hacer mejor y, por lo tanto, es la mejor opción. Según la complejidad relativa de la administración de colas de prioridad frente a la clasificación posterior, diría que la clasificación posterior debería ser más rápida. Pero de nuevo, deberías probar esto.

Estoy generando algunos elementos que necesito para ser ordenados al final. Me preguntaba, ¿qué es más rápido en términos de complejidad: insertarlos directamente en una cola de prioridad o una estructura de datos similar, o usar un algoritmo de clasificación al final?

Probablemente estamos cubiertos de esto arriba.

Sin embargo, hay otra pregunta que no hiciste. Y tal vez ya sabes la respuesta. Es una cuestión de estabilidad. El C ++ STL dice que la cola de prioridad debe mantener un orden "débil y estricto". Esto significa que los elementos de igual prioridad son incomparables y se pueden colocar en cualquier orden, a diferencia de un "orden total" donde cada elemento es comparable. (Aquí hay una buena descripción de la ordenación). En la clasificación, "débil estricto" es análogo a una ordenación inestable y "orden total" es análogo a una ordenación estable.

El resultado final es que si los elementos de la misma prioridad deben permanecer en el mismo orden en que los introdujo en su estructura de datos, entonces necesita una clasificación estable o un orden total. Si planea usar el C ++ STL, entonces solo tiene una opción. Las colas de prioridad utilizan un ordenamiento estricto y débil, por lo que son inútiles aquí, pero el algoritmo "stable_sort" en la biblioteca de algoritmos STL hará el trabajo.

Espero que esto ayude. Déjeme saber si desea una copia de cualquiera de los documentos mencionados o si desea una aclaración. :-)

Answer 8

Una cola de prioridad se implementa generalmente como un montón. En promedio, la clasificación mediante el uso de un montón es más lenta que la ordenación rápida, excepto que la ordenación rápida tiene un peor desempeño en el peor de los casos. También los montones son estructuras de datos relativamente pesadas, por lo que hay más sobrecarga.

Yo recomendaría una especie al final.

Answer 9

Insertar n elementos en una cola de prioridad tendrá una complejidad asintótica O ( n log n ), por lo que, en términos de complejidad, no es más eficiente que usar la sort una vez, al final.

Si es más eficiente en la práctica realmente depende. Necesitas probar. De hecho, en la práctica, incluso la inserción continua en una matriz lineal (como en la clasificación por inserción, sin construir un montón) puede ser la más eficiente, aunque asintóticamente tenga peor tiempo de ejecución.