c++ - tiene - ordenar un vector ascendentemente en java
¿Std:: sort comprueba si un vector ya está ordenado? (7)
¡Guauu! ¿Tuviste optimizaciones en todo el camino?
los resultados de su código en mi plataforma (tenga en cuenta los valores en el eje vertical).
Creo que el estándar de C ++ para std::sort no garantiza el rendimiento O (n) en una lista que ya está ordenada. Pero aún así, me pregunto si, a su entender, cualquier implementación de STL (GCC, MSVC, etc.) hace que la comprobación std::is_sorted ejecute antes de ejecutar el algoritmo de clasificación.
Preguntado de otra manera, ¿qué rendimiento se puede esperar (sin garantías, por supuesto) de ejecutar std::sort en un contenedor ordenado?
Nota al margen: publiqué algunos puntos de referencia para GCC 4.5 con C ++ 0x habilitado en mi blog. Aquí están los resultados:
¿Y por qué cualquier implementación verificaría eso? ¿Qué ganaría? - Nada en promedio. Una buena regla de diseño no es complicar la implementación con optimizaciones para casos de esquina que no hacen ninguna diferencia en promedio. Este ejemplo es similar a verificar la autoasignación. Una respuesta simple: no lo hagas.
Las implementaciones son libres de usar cualquier algoritmo de clasificación eficiente que deseen, por lo que depende en gran medida de la implementación.
Sin embargo, he visto una comparación de rendimiento de libstdc ++ como se usa en Linux y en contra de libc ++ la nueva biblioteca de C ++ desarrollada por Apple / LLVM. Ambas bibliotecas son muy eficientes en datos ordenados o revertidos (mucho más rápido que en una lista aleatoria) con la nueva biblioteca siendo considerablemente más rápida que la anterior y reconociendo muchos más patrones.
Para estar seguro, debería considerar hacer sus propios puntos de referencia.
Las sanciones estándar solo implementan std::sort con complejidad O (n log n):
Complejidad: Aproximadamente N log N (donde
N == last - first) comparaciones en promedio.
Ver la sección 25.3.1.1 Ordenar [lib.sort] (ISO / IEC 14882: 2003 (E)).
Por lo tanto, el conjunto de funciones de clasificación permitidas es limitado, y tiene razón en que no garantiza la complejidad lineal.
El comportamiento ideal para un género es O (n), pero esto no es posible en el caso promedio.
Por supuesto, el caso promedio no es necesariamente el caso exacto que tiene ahora, por lo que para los casos de esquina, no hay mucha garantía.
Le sugiero que lea esta comparación de algoritmos de clasificación , está muy bien hecho e informativo, compara una serie de algoritmos de clasificación entre sí y con la implementación de std :: sort de GCC. Notará, en los gráficos en el enlace dado, que el rendimiento de std :: sort para "casi ordenado" y "casi inverso" es lineal en la cantidad de elementos a ordenar, es decir, O (n). Por lo tanto, no hay garantía, pero puede esperar fácilmente que una lista casi ordenada se ordene en tiempo casi lineal. Pero, por supuesto, no hace una comprobación is_sorted, e incluso si ordena una matriz ordenada en tiempo lineal, no será tan rápido como hacer una comprobación is_sorted y omitir la ordenación por completo. Es su decisión determinar si es mejor verificar antes de ordenar o no.
No hay garantía de que verifique esto. Algunas implementaciones lo harán, otras probablemente no lo harán.
Sin embargo, si sospecha que su entrada ya puede estar ordenada (o casi ordenada), std::stable_sort podría ser una mejor opción.
No Además, no es lógico que se llame a is_sorted() para cualquier implementación de STL. Dado que, is_sorted() ya está disponible como independiente. Y es posible que muchos usuarios no quieran perder innecesariamente ciclos de ejecución para llamar a esa función cuando ya saben que su contenedor no está ordenado.
STL también debería seguir la filosofía de C ++: " pago por uso ".