¿Qué es más rápido: insertar en una cola de prioridad o clasificar de forma retroactiva?¿Qué es más rápido: insertar en una cola de prioridad o clasificar de forma retroactiva?
Estoy generando algunos elementos que debo ordenar al final. Me preguntaba, ¿qué es más rápido en términos de complejidad: insertarlos directamente en una prioridad_cola o una estructura de datos similar, o usar un algoritmo de ordenación al final?
Inserción n elementos en una cola de prioridad tendrá asintótica complejidad O (n registro n) por lo que en términos de complejidad, no es más eficaz que utilizar sort una vez, al final.
Si realmente es más eficiente en la práctica, realmente depende. Tienes que probar. De hecho, en la práctica, incluso inserción en una matriz lineal (como en la ordenación de inserción, sin construir un montón) puede ser la más eficiente, aunque asintóticamente tiene peor tiempo de ejecución.
Creo que la inserción es más eficiente en casi todos los casos en los que está generando datos (es decir, no los tiene en una lista).
Una cola de prioridad no es su única opción para la inserción sobre la marcha. Como se menciona en otras respuestas, un árbol binario (o árbol RB relacionado) es igualmente eficiente.
También verificaría cómo se implementa la cola de prioridad: muchas están basadas en b-trees, pero algunas implementaciones no son muy buenas para extraer los elementos (básicamente pasan por toda la cola y buscan la prioridad más alta) .
Una cola de prioridad generalmente se implementa como un montón. La ordenación con un montón es, en promedio, más lenta que la del servicio rápido, excepto que la oferta rápida tiene un peor rendimiento en el peor de los casos. Además, los montones son estructuras de datos relativamente pesadas, por lo que hay más sobrecarga.
Lo recomiendo ordenar al final.
Relativamente pesado? No, es una matriz simple, y las operaciones de tamizado y burbujeo son igualmente simples. La razón por la cual el quicksort es más rápido en promedio está más relacionado con el hecho de que heapsort tiene que reubicar cada elemento al menos dos veces (funciona en dos pasos). Sin embargo, este no es el caso aquí, ya que hacemos la clasificación en línea, por lo que los tiempos de ejecución relativos de heapsort y quicksort en este contexto deben ser reevaluados cuidadosamente. –
Depende de los datos, pero generalmente me parece que InsertSort es más rápido.
Tenía una pregunta relacionada, y al final me di cuenta de que el cuello de botella era solo porque estaba haciendo una clasificación diferida (solo cuando terminé necesitándola) y en una gran cantidad de artículos, usualmente tenía el peor- escenario posible para mi QuickSort (ya en orden), , así que utiliza un inserto tipo
Sorting 1000-2000 elements with many cache misses
Así analizar sus datos!
¿Por qué no utilizar 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 balanceados de RedBlack here
Creo que las colas de prioridad serán trivialmente más eficientes que los intentos binarios autoequilibrantes, ya que estos últimos no ofrecen el mismo comportamiento amigable con el caché y dependen de la asignación de la memoria del montón. –
@Konrad: parece ser el resultado de mi prueba simplista. De hecho, esperaba que el multiset fuera horrible, precisamente por la asignación de memoria, pero no es * tan * malo, solo cinco veces más lento que 'std :: sort'. –
Para su primera pregunta (que es más rápida): depende. Solo pruébalo. Suponiendo que se desea que el resultado final en un vector, las alternativas podrían ser algo como esto:
#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
Así, std::sort latidos std::priority_queue, en este caso.Pero tal vez tengas una mejor o peor std:sort, y tal vez tengas 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 caso de std::sort, por lo que en cierto modo esta prueba podría halagarlo. Pero para una buena implementación de std::sort, su peor caso será muy difícil de construir, y en realidad podría no ser del todo malo.
Edit: añadido 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
Para su segunda pregunta (complejidad): todos son O (n log n), haciendo caso omiso de aplicación incómoda detalles 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 "clasificación" se entiende una clasificación de comparación. Otros tipos de género pueden tener una complejidad menor.
¿Por qué poner los elementos de la cola en un vector? –
@static_rtti: solo porque no sé lo que quieres hacer con ellos, entonces estoy haciendo algo. Es necesario hacer todos los pops para evaluar la velocidad de la cola de prioridad, pero supongo que no tuve que usar los valores. Dudo que agregarlos al vector requiera mucho más tiempo en comparación con el 'pop' en sí, pero debe ejecutar su propia prueba lo más cerca posible de su uso real. –
¡Gracias por las pruebas! –
Por lo que tengo entendido, su problema no requiere la cola de prioridad, ya que sus tareas suenan como "hacer muchas inserciones, después de eso ordenar todo". Es como disparar pájaros desde un láser, no es una herramienta adecuada. Use técnicas de clasificación estándar para eso.
Necesitaría una cola de prioridad, si su tarea era imitar una secuencia de operaciones, donde cada operación puede ser "Agregar un elemento al conjunto" o "Eliminar el elemento más pequeño/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.
En un max-inserción operaciones de la cola de prioridad son O (lg n)
Bienvenido a Stack Overflow. Su respuesta es precisa hasta donde llega, pero no hace una comparación de las dos técnicas sobre las que pregunta. Por ejemplo, si realiza N inserte operaciones en una cola de prioridad, entonces tiene operaciones O (N lg N); si ordena los datos de forma retrospectiva, normalmente también tiene operaciones O (N lg N). Por lo tanto, la comparación implicará el análisis de las constantes, lo cual es complicado. –
Esto probablemente se trata de un poco tarde en el juego en lo que se refiere a su pregunta, pero vamos a ser completa.
Las pruebas son la mejor manera de responder a esta pregunta para la arquitectura, el compilador y la implementación 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 O (1) hora. La publicación de Beucher y Meyer de 1992 "El enfoque morfológico de la segmentación: la transformación de la cuenca hidrográfica" describe las colas jerárquicas, que funcionan bastante rápido para valores enteros de rango limitado. La publicación de Brown de 1988 "Colas de calendario: una rápida implementación de cola de prioridad de 0 (1) para el problema de conjunto de eventos de simulación" ofrece otra solución que trata bien con rangos de enteros más grandes: dos décadas de trabajo después de la publicación de Brown han producido algunos buenos resultados para hacer números enteros colas de prioridad rápido. Pero la maquinaria de estas colas puede complicarse: los tipos de cubo y los tipos de raíz aún pueden proporcionar una operación O (1). En algunos casos, incluso puede cuantizar datos de coma flotante para aprovechar una cola de prioridad O (1).
Incluso en el caso general de datos de coma flotante, ese O (n log n) es un poco engañoso.El libro de Edelkamp "Búsqueda Heurística: Teoría y Aplicaciones" tiene la siguiente tabla útil que muestra la complejidad del tiempo para diversos algoritmos de cola de prioridad (recuerde, colas de prioridad son equivalentes a la clasificación y gestión montón):
Como se puede ver, muchas colas de prioridad tienen costos de 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 descarta para medir la complejidad de tiempo de un algoritmo, aún vale la pena conocer estos costos.
Pero todas estas colas aún tienen complejidades de tiempo que son comparables. ¿Cuál es el mejor? Un documento de 2010 de Cris L. Luengo Hendriks titulado "Revisando colas de prioridad para el análisis de imágenes" aborda esta cuestión.
En la prueba de retención Hendriks', una cola de prioridad se sembró con N números aleatorios en el intervalo [0,50]. El elemento que estaba en la parte superior de la cola se quitó de la cola, se incrementó en un valor aleatorio en el rango [0,2], y luego se puso 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 funcionaron 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 se puede ver, las diferentes colas menudo tenían respuestas muy diferentes a encolamos y desencolado. Estas cifras implican que si bien puede haber algoritmos de cola de prioridad que son superiores para la operación continua, no existe la mejor opción de algoritmo para simplemente llenar y luego vaciar una cola de prioridad (la operación que está haciendo).
Vamos a mirar hacia atrás en sus preguntas:
Lo que es más rápido: la inserción en una cola de prioridad, o clasificar de forma retrospectiva?
Como se muestra arriba, las colas de prioridad se pueden hacer eficientes, pero todavía hay 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, además el vector es O (n) para ser leído.
Ordenar el vector le costará O (n log n) suponiendo que tiene datos de coma flotante, pero esta vez la complejidad no oculta cosas como las colas de prioridad. (Hay que tener un poco de cuidado, sin embargo, Quicksort funciona muy bien con algunos datos, pero tiene una complejidad de tiempo de peor caso de O (n^2). Para algunas implementaciones, este es un riesgo de seguridad serio.)
Me temo que no tengo datos para los costos de clasificación, pero diría que la clasificación retroactiva captura la esencia de lo que intentas hacer mejor y, por lo tanto, es la mejor opción. En función de la complejidad relativa de la gestió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 debo ordenar 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 ordenación al final?
Probablemente este tema esté cubierto anteriormente.
Sin embargo, hay otra pregunta que no hizo. 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 "estrictamente débil". Esto significa que los elementos de igual prioridad son incomparables y pueden colocarse en cualquier orden, a diferencia de un "orden total" donde cada elemento es comparable. (Hay una buena descripción del pedido here). En la clasificación, "estricto débil" es análogo a un tipo inestable y "orden total" es análogo a un tipo estable.
El resultado es que si los elementos de la misma prioridad se mantienen en el mismo orden en que los insertó en su estructura de datos, entonces necesita un orden estable o un orden total. Si planea usar C++ STL, entonces tiene solo una opción. Las colas de prioridad utilizan un ordenamiento débil estricto, por lo que son inútiles aquí, pero el algoritmo "stable_sort" en la biblioteca de algoritmo STL hará el trabajo.
Espero que esto ayude. Avíseme si desea una copia de cualquiera de los artículos mencionados o si desea una aclaración. :-)
¡Gracias por esta gran respuesta! –
Encontré otro documento interesante pero más antiguo de 2007 "Estudio experimental de colas de alto rendimiento con prioridad". Hace referencia a al menos una estructura de datos de alto rendimiento de Peter Sanders llamada secuencia de almacenamiento http://algo2.iti.kit.edu/sanders/papers/falenex.ps.gz http://www.mpi-inf.mpg.de/ ~ lijadoras/programas/spq/ – Karussell
Wow. Me encanta SO porque hay personas como tú –
¿Alguna información sobre la cantidad de datos? ¿necesita una ordenación/clasificación completa o una ordenación parcial/nth_element sería suficiente? – MadH
Necesito un tipo completo, pero no tiene que ser estable. Estoy más interesado en la complejidad que en el rendimiento para un tamaño de problema específico, por lo que no especifiqué ninguno. –
casi un duplicado (pero para Java, por lo que no voté para cerrar): http://stackoverflow.com/questions/3607593/is-it-faster-to-add-to-a-collection-then-sort- it-or-add-to-a-sorted-collection – Thilo