Y más sobre tipos

Me aventuraría a volver a plantear este tema. Comenzaré con un enlace a un artículo de Mikhail Opanasenko (oms7) , que es muy impresionante en términos de la cantidad de trabajo realizado, así como en la cantidad de enlaces citados. Comenzó a preparar su material, sin saber acerca de esta publicación, que posteriormente, después de la familiarización, llevó a la necesidad de un procesamiento sustancial. Para aquellos que ya han leído este artículo, les informo que en mi material, se estudian tipos más diversos de datos, en particular, cadenas y números reales, se utilizan las bibliotecas de impulso y bsd, y se mencionan algunos otros temas que faltan en el artículo.

Hay docenas de formas diferentes de organizar los elementos de datos en orden. Entre ellos, hay aquellos que funcionan rápido, de modo que, por ejemplo, pueden ordenar cualquier matriz de datos ubicada en la RAM de la computadora en un máximo de minutos. Más específicamente, se puede decir que la clasificación rápida organiza mil millones de enteros en una buena computadora personal moderna en menos de cien segundos. Si utiliza métodos primitivos y no rápidos, por ejemplo, clasificación de burbujas o clasificación de selección, para clasificar un mayor número de elementos, entonces el tiempo dedicado a dicho procesamiento de datos puede exceder cualquier expectativa; dicho "procesamiento" en realidad puede llevar varios días, semanas e incluso años. Esta gran diferencia es causada por el hecho de que el tiempo de clasificación por métodos rápidos es aproximadamente proporcional a N log N , y primitivo - N ² . Con el aumento de N, la diferencia entre los dos valores se vuelve muy notable. Por lo tanto, es razonable usar métodos primitivos solo para trabajar con datos pequeños, por ejemplo, en computadoras modernas, hasta varios miles de elementos. También es natural usarlos para enseñar los conceptos básicos de programación y pensamiento lógico, ya que son mucho más simples que los métodos rápidos.

Me gustaría entender los métodos de clasificación existentes en las bibliotecas estándar actuales. Descubra cuán grande es la diferencia entre ellos en términos de sus características principales, velocidad de trabajo y también sus características. Además, consideraremos en el camino para la comparación y ejercicios para la mente algunos métodos que no son difíciles de implementar. También vale la pena señalar que el optimizador del compilador GCC y posiblemente otros compiladores buenos funcionan muy bien, acelerando el código varias veces (a veces incluso más de 5 veces).

Comencemos con el método de clasificación de burbujas como el más simple y el más lento. De acuerdo con este método, debe recorrer la matriz de datos una y otra vez, comparar elementos vecinos y cambiar sus lugares si se rompe el orden entre ellos. Después de cada pasada, al menos un elemento (el más grande o el más pequeño, depende del orden seleccionado) está en su lugar. Además de la simplicidad, este método tiene una ventaja más; no requiere memoria adicional. Se puede observar una característica más del método de burbuja: procesa muy rápidamente los datos ya ordenados y, en algunos casos, lo convierte en uno de los métodos más rápidos. Si los datos están ordenados solo parcialmente, entonces este método funciona con ellos más rápido, pero en la mayoría de los casos solo muy ligeramente. Para las pruebas, utilicé la siguiente implementación .

Otro método lento es el tipo de selección. Aquí, en cada pasada, primero se encuentran los elementos más grandes y más pequeños en los datos y luego estos elementos se colocan en las posiciones extremas correspondientes al orden seleccionado. En la próxima pasada, clasificamos los datos sin estos elementos extremos. Este método es tan simple como la clasificación de burbujas, y tampoco requiere memoria adicional, pero es notablemente más rápido. Además, la clasificación mediante este método realiza un número mínimo de registros de permutaciones de elementos de datos. Por lo tanto, cuando las permutaciones son mucho más lentas que las comparaciones, el pedido por el método de selección puede ser aceptable si el número de elementos de datos es pequeño. Aquí está mi implementación . Más a menudo, esta clasificación se realiza, colocando en su lugar solo un elemento por pase. La clasificación en montón (o piramidal), que se discutirá más adelante, es la versión más avanzada de la clasificación en cuestión.

El código para el último método lento considerado, la ordenación por inserción, es probablemente el más corto de todos los códigos que implementan la ordenación, por lo que este método a veces es usado por ordenaciones rápidas complejas para casos en los que el número de elementos a ordenar es pequeño (varias decenas). Es algo similar a ordenar por una burbuja, ya que aquí y allá los elementos vecinos se comparan sucesivamente. Pero la ordenación por inserciones busca el siguiente elemento para la posición correcta en la parte ya ordenada de los datos, y no solo empuja el elemento extremo a la posición extrema. Con este enfoque, tampoco se necesita memoria adicional. Al igual que la clasificación por burbujas, la clasificación por inserción es muy rápida en datos ordenados y más rápida en datos parcialmente ordenados. En este último caso, significativamente más rápido que la burbuja. Por lo general, ordenar por inserciones es algo más rápido que ordenar por selección. Y a diferencia de este último, como la clasificación de burbujas, es estable. Lo peor de todo es que la ordenación por inserción funciona con datos en orden inverso, con lo que a veces se convierte en el más lento de los más lentos. Para las pruebas, se utilizó la siguiente implementación . Se puede acelerar un poco si no utiliza búsqueda lineal, sino binaria, por ejemplo, usando la función std :: bsearch. Se puede lograr una aceleración significativa mediante el uso de una estructura de tipo de lista, la inserción de un elemento en el que es muy rápido. También puede notar que esta es la clasificación más natural: por ejemplo, generalmente se usa intuitivamente cuando se juega a las cartas.

La clasificación de shell es la más simple entre los métodos rápidos y es bastante adecuada para los estudiantes que recién comienzan a aprender programación. Es solo una modificación de la clasificación de burbujas. La única diferencia entre ellos es que en la clasificación de Shell, la distancia entre los elementos comparados se toma de pasillo en pasillo, de mayor en la primera pasada, a 1 en la última, por lo que el método de Shell degenera en una clasificación de burbujas primitiva en estas últimas pasadas. Donald Shell publicó el algoritmo de clasificación básico que obtuvo su nombre en 1959. Por lo tanto, esta es una de las primeras clasificaciones universales que funcionan rápidamente. A modo de comparación, el algoritmo de clasificación rápida se publicó dos años después, y la clasificación popular o introspectiva de Tim se conoció solo en los años 90. Varios problemas matemáticos interesantes sin resolver están asociados con la clasificación de Shell, el principal de los cuales es cómo seleccionar de manera óptima los desplazamientos entre los elementos comparados. Se encontraron algunas secuencias de registro, por ejemplo, A102549 . Tales secuencias se encuentran a través de cálculos colosales, por lo que tienen una longitud muy corta, A102549 tiene solo 8 elementos, lo cual es suficiente solo para datos de hasta aproximadamente 3,000 elementos. Para Big Data, las secuelas deben verse casi al azar. Los valores usados ​​cercanos a las potencias de 2, e , 2.25 y 3. Los números primos cercanos a las potencias de 2 mostraron los peores resultados, notablemente inferiores a los mejores. Pero las otras tres opciones resultaron ser aproximadamente las mismas en términos de impacto en el rendimiento y probablemente muy cerca de lo óptimo. Además, en estos tres casos, el uso de números primos no dio ventajas tangibles. Es curioso que los sesgos propuestos en Wikipedia (con una base de 2.25) basados ​​en referencias a los trabajos correspondientes no mostraron los mejores resultados en las pruebas, aunque sus diferencias con los mejores fueron muy insignificantes (no más del 5-10%). El uso de A102549 como punto de partida tampoco dio resultados notables. Mikhail Opanasenko también trató de desentrañar la clasificación de Shell y obtuvo un resultado interesante de que los desplazamientos elegidos por la fórmula s _{n + 1} = 10s _n / 3 dan un efecto muy bueno y tal vez incluso cerca del ideal. Mis resultados confirman esto. En muchos casos, fueron tales sesgos los que dieron el mejor resultado, aunque este no fue siempre el caso y la brecha con el resultado más cercano fue bastante pequeña (alrededor del 5%). Mi código para implementar clasificaciones de Shell utiliza tablas pequeñas con compensaciones, aunque si no usa números primos, estas compensaciones para tablas se pueden calcular casi instantáneamente, como se hizo en la implementación de una de las variantes dadas de esta clasificación.

Es interesante que si tomamos las compensaciones cercanas a las potencias de los triples de una manera ligeramente diferente y usamos un algoritmo ligeramente diferente (ver implementación ), entonces en números de 32 bits obtendremos velocidades cercanas a las mejores, pero en números más largos y en las líneas obtendremos una desaceleración significativa, a veces Más del 100%. Los resultados para el mejor algoritmo utilizado por oms7 también se encuentran en la tabla a continuación, pero aunque muestra buenos resultados en orden, está muy por detrás de los líderes en términos de valores absolutos.

¿Habrá alguna manera de encontrar las mejores compensaciones? Quizás, pero me atrevo a sugerir que no sea pronto. La ordenación de shell se usa en el kernel de Linux, y en al menos una biblioteca C su código se usa para la función qsort () estándar. Se ha demostrado teóricamente que la velocidad de clasificación óptima de Shell en orden es solo un poco más lenta que los métodos logarítmicos rápidos "reales". De hecho, la dependencia del tiempo promedio de procesamiento de datos en su tamaño para la clasificación óptima de Shell se describe mediante la fórmula on N (log N / log log N ) ² , que incluso para N muy grande está muy cerca de la fórmula ∽ N log N típica para otros métodos rápidos. Por lo general, la ordenación de Shell a menudo es incluso más rápida que los métodos teóricamente más rápidos en orden y solo comienza a ceder ligeramente cuando se procesan matrices bastante grandes (del orden de 10 millones de elementos). Esta clasificación absolutamente no necesita memoria adicional y se comporta de manera estable para una amplia variedad de opciones para llenar datos, comparándose favorablemente con clasificaciones rápidas. El método Shell no posee la propiedad de estabilidad.

La ordenación rápida es solo un poco más compleja que el algoritmo de Shell y sigue siendo una de las formas más rápidas de organizar datos dispersos aleatoriamente. Sin embargo, esta clasificación tiene varios inconvenientes. Necesita memoria adicional y, en casos muy raros, funciona extremadamente lento, según una dependencia cuadrática. La idea principal de este método es dividir los datos en dos partes: los datos en una parte deben ser más o menos (depende del orden seleccionado) que en la otra. Existen varios métodos para esta separación. Idealmente, con cada división, ambas partes deben tener aproximadamente el mismo tamaño, y lo peor de todo, cuando una de las partes se compone de un solo elemento durante la división. Consideremos varias implementaciones de algoritmos de ordenación rápida, en particular, el método Hoar , en el que un elemento de referencia que divide los datos en dos partes se selecciona desde el medio de los datos ordenados.

También consideramos el algoritmo extremadamente compacto de Lomuto , que a veces es un poco (aproximadamente 1%) más rápido que el método Hoare considerado. Sin embargo, en casos especiales típicos, por ejemplo, en datos ordenados, inversos o malvariantes, el método de Lomuto muestra una lentitud extrema. Además, entre las opciones consideradas para la ordenación rápida, resultó ser el más codicioso para el tamaño de la pila durante las ejecuciones prácticas: al ordenar matrices relativamente pequeñas, solo este tipo no tenía suficientes 8 megabytes para la pila, tuve que establecer este tamaño a través de ulimit more. Tal avaricia por la pila conduce a grandes ralentizaciones cuando se procesan grandes datos (decenas de millones de líneas), y tengo dificultades para llamar a su naturaleza. Solo puedo afirmar que es mejor no utilizar esta clasificación del siguiente párrafo con dichos datos.

El método Lomuto selecciona el último elemento como referencia, pero es posible implementar una ordenación rápida sin ningún elemento de soporte , más precisamente, la selección de tal elemento aquí ocurre como resultado de la bisección de datos ya realizada. Esta clasificación por características de velocidad resultó estar cerca del método de Lomuto, aunque generalmente es un poco más rápido, y en casos extremos es notablemente más rápido que Lomuto, pero más lento que Hoar.

En 2009, se publicó un algoritmo de clasificación rápida de dos anclajes, que se convirtió en estándar para el lenguaje Java. Este algoritmo reduce el número de permutaciones en un 20% en comparación con los mejores típicos, pero el número de comparaciones no cambia. Su autor es Vladimir Yaroslavsky. Realmente funciona, como regla, más rápido que otros tipos rápidos. Lo optimicé un poco, utilizando el hecho conocido desde hace mucho tiempo de que en la arquitectura x86, el intercambio generalmente funciona más rápido que la asignación, y para las cadenas C ++ es mucho, mucho más rápido. Todas las clasificaciones rápidas consideradas hasta ahora no tienen la propiedad de estabilidad.

Se necesita memoria adicional para una clasificación rápida para organizar llamadas recursivas. Sin embargo, la segunda llamada de este tipo puede ser reemplazada por un bucle, al optimizar la recursión de la cola , que en términos de velocidad puede no dar ganancias, pero reduce significativamente el tamaño de los datos adicionales utilizados. Implementé la opción de clasificación Hoar con esta optimización. Además, en los programas del sistema, puede verificar el puntero de la pila y si se acerca a un valor crítico, simplemente puede restablecer todas las llamadas recursivas y comenzar a ordenar nuevamente; para este caso, es obvio que necesita usar la opción de clasificación rápida que no se ralentiza en datos casi ordenados, por ejemplo , la versión propuesta anteriormente de Hoar. Combatir el uso de memoria adicional puede considerarse la idea principal de la clasificación rápida de la biblioteca de lenguaje C estándar en GCC. Generalmente abandonó la recursión. En cambio, usan su simulación, que permite que un tercero reduzca la carga en la pila. El código resultó bastante grande, unas 150 líneas. Acerca de esta clasificación, todavía habrá un poco de material a continuación.

La clasificación de hash puede ser muy rápida, cercana a ∽ N. Sin embargo, a veces puede funcionar en una dependencia cuadrática. La velocidad de este método de clasificación depende mucho de la entrada. Si la función hash distribuye los datos de manera uniforme sobre la matriz auxiliar, obtenemos la relación lineal más rápida. Y si todos los datos se agrupan cerca de varios "centros de masa" muy separados o cuando hay muchos elementos de datos idénticos, es decir, cuando ocurren muchas colisiones de hash, obtenemos la peor dependencia de tipo ∽ N ² . Al igual que con la ordenación de árboles, para ordenar el hash, necesita una gran cantidad de datos adicionales, en la lista de códigos a continuación necesita, por ejemplo, 12 bytes adicionales para cada entero ordenable (int32, x86-64). Una propiedad interesante de la clasificación hash es la ausencia de operaciones de comparación entre elementos de datos, lo que distingue esta clasificación de todos los considerados anteriormente. Más precisamente, estas operaciones son necesarias solo para colisiones. Al ordenar los datos donde la clave coincide con el elemento de datos completo, puede usar un contador adicional para el número de elementos idénticos, pero esta es una optimización bastante dudosa. También puede usar un árbol binario en lugar de una lista para almacenar datos de colisiones hash, esto acelera enormemente el trabajo para casos particulares individuales cuando hay muchas colisiones, pero en general, cuando se usa un árbol binario, en muchos casos se ralentiza y esto a pesar del hecho de que en este caso el elemento los datos tienen que almacenar casi 100 bytes de información adicional. Implementé tres opciones para la clasificación hash usando un árbol binario: uno usa un árbol desordenado y los otros dos usan árboles estándar de las bibliotecas std y boost. La ordenación hash es prácticamente inadecuada para ordenar cadenas de texto, excepto las muy cortas, ya que es imposible hacer una buena función hash para dichos datos. No pude adaptar el hash estándar de C ++ (unordered_multiset) para ordenar: intenté usar funciones hash monótonas y ordenar relaciones en lugar de igualdad; esto no funcionó.

La ordenación de matrices es muy similar a la anterior. También se usa una matriz auxiliar, donde los valores son ingresados ​​por la función hash. En caso de colisión, es necesario desplazar el fragmento continuo de los elementos ocupados a la posición izquierda o derecha, liberando la posición indicada por la función hash para el nuevo elemento. Para obtener una buena velocidad, es necesario que la matriz auxiliar sea varias veces (de 2-3) más que la original. Con un aumento en el tamaño de la matriz auxiliar, la velocidad aumenta solo hasta un cierto límite, dependiendo de los datos ordenados y la función hash asociada a ellos, y luego (típicamente de 4 a 5) disminuye. La velocidad de operación es casi la misma que la del hash, pero en datos buenos un poco más rápido y en datos malos es notablemente más lento. Este tipo también necesita mucha memoria extra.Si limitamos el número de elementos en la matriz ordenada a un poco más de cuatro mil millones, entonces una matriz auxiliar triple requerirá la misma cantidad de datos adicionales que la clasificación con un hash, y una triplicada requerirá 28 bytes, que es notablemente menor que para ordenar por un árbol, o mucho menos que un hash con arboles. Esta clasificación también es casi inadecuada para trabajar con cadenas. No hay un artículo de Wikipedia sobre dicho algoritmo, pero aquí está mi implementación .

Curiosamente, en Wikipedia, en un buen artículo general , no se mencionan métodos intermedios como la ordenación de matrices y el hash, que naturalmente se pueden colocar entre métodos basados ​​en la comparación de elementos y métodos basados ​​en el valor absoluto de los elementos.

Una de las clasificaciones más rápidas, que nunca utiliza comparaciones en absoluto, es la clasificación por bits conocida desde el siglo XIX.(clasificación de radix). Su idea es muy simple: debe trabajar con grupos de bits de representación de datos (para las pruebas tomé grupos de 8, 11 y 16 bits). Se crean tablas para cada grupo, y los resultados se combinan de una manera relativamente simple. Hay dos formas principales de utilizar la ordenación por bits. Es más conveniente tomar los dígitos para ordenar los números de derecha a izquierda (esta es la opción LSD - Dígito menos significativo), y para ordenar las cadenas de izquierda a derecha (esta es la opción MSD - Dígito más significativo). La ordenación a nivel de bits suele ser significativamente más rápida que cualquier otro método de ordenamiento de datos. Sorprendentemente, el soporte para la ordenación bit a bit todavía no es muy significativo: no está ni en boost ni en la biblioteca estándar de C ++, ni siquiera conozco su versión para ninguna biblioteca conocida para trabajar con números o cadenas de C ++. Este tipo tienepor supuesto, y desventajas. Es muy sensible al tipo de datos para la clasificación, por ejemplo, necesita tener su propia versión de dicha clasificación para datos de cada tamaño, debe hacer opciones especiales para enteros sin signo y con signo, y el soporte para trabajar con números reales puede requerir un poco de esfuerzo. Cuando se usa el orden del byte menos significativo al más importante, su variante generalmente requiere memoria adicional, un poco más que para los datos iniciales (esto es significativamente menor que para ordenar por un hash o una matriz, y aún más por un árbol). Además, esta opción es de poca utilidad para ordenar cadenas largas. Mi código para este tiponecesita hacer opciones especiales para enteros sin signo y con signo, y el soporte para trabajar con números reales puede requerir bastante esfuerzo. Cuando se usa el orden del byte menos significativo al más importante, su variante generalmente requiere memoria adicional, un poco más que para los datos iniciales (esto es significativamente menor que para ordenar por un hash o una matriz, y aún más por un árbol). Además, esta opción es de poca utilidad para ordenar cadenas largas. Mi código para este tiponecesita hacer opciones especiales para enteros sin signo y con signo, y el soporte para trabajar con números reales puede requerir bastante esfuerzo. Cuando se usa el orden del byte menos significativo al más importante, su variante generalmente requiere memoria adicional, un poco más que para los datos iniciales (esto es significativamente menor que para ordenar por un hash o una matriz, y aún más por un árbol). Además, esta opción es de poca utilidad para ordenar cadenas largas. Mi código para este tipoEsta opción no es adecuada para clasificar cadenas largas. Mi código para este tipoEsta opción no es adecuada para clasificar cadenas largas. Mi código para este tipoaquí , se basa en el código del artículo oms7 mencionado. La opción de orden de byte inverso es más versátil y muy adecuada para clasificar cadenas. Esta opción se puede implementar sin el uso de memoria adicional (el precio por esto es la pérdida de la propiedad de estabilidad), como se hace en la función radixsort () de la biblioteca bsd. Mi codigopara esta opción, también se basa en el código oms7, usa memoria adicional, datos de origen un poco más grandes, tiene la propiedad de estabilidad, pero no está optimizado para cadenas y, por lo tanto, muestra características de rendimiento significativamente peores que la función similar sradixsort () de la biblioteca bsd ya mencionada . Esta clasificación puede mostrar resultados sorprendentemente pobres cuando se trabaja con matrices numéricas pequeñas, trabajando varios órdenes de magnitud más lentamente que incluso la burbuja, aunque estamos hablando de valores muy pequeños de no más de unos pocos milisegundos y esta diferencia no es fácil de notar. Esto se debe al hecho de que utiliza matrices auxiliares de tamaño pequeño, pero al ordenar datos de tamaño pequeño, estos tamaños pequeños pueden ser más grandes que los datos ordenados.Para evitar ralentizaciones, la opción "de izquierda a derecha" utiliza la clasificación de inserción en lugar de la principal en estos casos. En conclusión, vale la pena señalar que esta es la única clasificación relativamente popular conocida que siempre funciona de manera confiable a una velocidad de ∽N , pero el coeficiente de proporcionalidad aquí depende del tamaño de los elementos de datos y para cadenas o números largos puede ser bastante notable.

Una opción para la clasificación MSD bit a bit es la clasificación por haz , una estructura de datos que le permite colocar de manera eficiente las claves de una matriz asociativa. Mi implementación , a pesar de optimizar el uso de la memoria, resultó ser muy codiciosa. Por velocidad, se obtuvieron los mejores resultados al clasificar las líneas largas.

Además, consideraremos algunas clasificaciones que se pueden encontrar en las bibliotecas estándar.

Comencemos con el rápido de la biblioteca estándar de C (qsort, una variante de GCC), ya escribí sobre eso. Solo puedo agregar aquí que esta clasificación, así como otras clasificaciones en C (por ejemplo, las siguientes de la biblioteca BSD) no son adecuadas para trabajar con datos de objetos, en particular, cadenas de C ++, que se debe al hecho de que dichos datos no son POD. Teniendo la fuente, el problema se puede resolver fácilmente reemplazando las operaciones de memcpy con asignaciones regulares. También puede observar que en algunas bibliotecas C estándar, esta clasificación no necesariamente es rápida, sino que puede reemplazarse por otras. En la versión actual para GCC, esta clasificación incluso tiene la propiedad de estabilidad. A veces hubo sorpresas con las clasificaciones en C mencionadas durante la recopilación de datos, por ejemplo, cuando se trabaja con el tipo std :: vector a través de un objeto funcional, podrían crear dificultades; puedo recomendar usarlo con datos de objetos con precaución. Según las corridas, esta clasificación a veces es relativamente lenta: es notablemente inferior en velocidad a otras implementaciones de clasificación rápida cuando se trabaja con números, pero cuando se trabaja con cadenas si es mejor, solo ordenar con dos puntos de control a veces lo adelanta,pero en líneas largas, el qsort estándar casi siempre lo supera. Lo más interesante fue descubierto cuando intenté ordenar mil millones de enteros con su ayuda: resultó que completar el tipo 7 conduce a una dependencia del tiempo cercana a una ley cuadrática, es decir, a un posible "procesamiento" que dura varios años (no esperé el final y lo detuve a las 21 horas de carrera). Con menos datos, esta clasificación generalmente puede seleccionar puntos de anclaje con los que funciona rápidamente.Con menos datos, esta clasificación generalmente puede seleccionar puntos de anclaje con los que funciona rápidamente.Con menos datos, esta clasificación generalmente puede seleccionar puntos de anclaje con los que funciona rápidamente.

La ordenación introspectiva se utiliza en la biblioteca estándar de C ++, aunque el método exacto utilizado en std :: sort depende de la implementación, siempre que se proporcione información sobre GCC. Según las corridas, este es el segundo más rápido después de la clasificación de dispersión cuando se trabaja con números, y la ventaja de la clasificación de dispersión es pequeña (de casi 0 a 30%), pero con la clasificación de cadenas todo es mucho peor: puede ser 3-4 veces menor que los líderes . En realidad, se trata de una clasificación rápida, en la que se tienen en cuenta dos casos especiales: 1) si el número de recursiones se ha vuelto demasiado grande, se produce el cambio a la clasificación por montón; 2) si el número de elementos para la clasificación es pequeño, se produce el cambio a la clasificación por inserciones. Clasificación

estable de la biblioteca estándar de C ++ ( std :: stable_sort), como su nombre lo indica, tiene la propiedad de estabilidad: conserva el orden relativo entre elementos con la misma clave. Esta propiedad es relativamente rara vez necesaria, aunque escribo sobre ella sin fundamento, solo en base a mi propia experiencia. Puede usar memoria adicional, lo que lo hace más rápido. Sorprendentemente, esta clasificación suele ser más rápida que std :: sort.

En el lenguaje python súper popular, la clasificación de Tim se usa como estándar . Para las pruebas, utilicé su versión del repositorio de github. Muestra buenos resultados récord en datos parcialmente ordenados, pero en promedio sigue siendo notablemente más lento que los líderes. Por lo general, su velocidad es el promedio entre la clasificación rápida y la clasificación de Shell, aunque en líneas generales a veces está cerca de los líderes. Tiene la propiedad de la estabilidad. Implementa un algoritmo relativamente complicado, en cuya implementación estándar se descubrió un error en 2015, que, sin embargo, requiere una situación poco realista para su manifestación.

La biblioteca BSD C tiene ordenación bit a bit ( radixsort) y su versión estable (sradixsort). Desafortunadamente, estos dos tipos solo se pueden usar para C-strings. Como se verá en los datos de prueba, esta es la forma más rápida de ordenar cadenas hoy en día y, por lo tanto, es sorprendente que no haya una opción estándar para las cadenas de C ++.

La biblioteca cuenta con más de BSD C especie de combinación ( el mergesort) Esta clasificación se conoce como una de las más rápidas para el acceso secuencial a datos (archivos, listas) y probablemente se usa en la biblioteca estándar de C ++ para ordenar listas (std :: list y std :: forward_list). Por cierto, era conocida desde 1948 y uno de sus desarrolladores era un matemático muy conocido y especialista en los primeros sistemas informáticos von Neumann. De los métodos rápidos, esta clasificación no se distingue por las mejores características, aunque, por regla general, es algo más rápida que los métodos Shell. Requiere memoria adicional y generalmente se implementa de manera sostenible.

Además, todavía hay clasificación por grupo(montón). El montón generalmente se usa para una cola óptima con prioridades, pero también se puede usar para ordenar. Los montones de clasificación no requieren memoria adicional, pero no tienen la propiedad de estabilidad. En velocidad para los números, es significativamente (hasta 3-6 veces) más lento que los métodos de Shell, pero para líneas de líneas no muy cortas, muestra muy buenos resultados, superando (al aumentar la longitud de la línea, la ventaja crece) métodos de Shell.

La ordenación del montón también está disponible en la biblioteca estándar de C ++. Dicha clasificación se realiza en dos operaciones: construir el montón (std :: make_heap) y luego ordenar ( std :: sort_heap)) Aquí, a diferencia de la biblioteca bsd, la ordenación es solo una de las operaciones para el montón. Por lo general, esta opción de clasificación es ligeramente más rápida que la anterior (la opción bsd muestra mejores resultados solo en números cortos y líneas s largas).

Usando la biblioteca estándar de C ++, puede ordenar el árbol equilibrado binario (std :: multiset), simplemente llene el árbol y luego dé la vuelta. Este método puede considerarse una clasificación rápida no recursiva. Surge un problema en el hecho de que el asignador de memoria estándar es notable por ser lento, por lo que para obtener los mejores resultados necesita usar su propio asignador, que se acelera en aproximadamente un 10-30%. También se puede observar que dicho método requiere una gran cantidad de memoria adicional, con g ++ para cada elemento de datos, además de eso, también debe almacenar 32 bytes (en la arquitectura x86-64); sería interesante intentar almacenar dicho árbol como un montón, es decir, sin más byte Si usa boost :: container :: multiset, necesita menos memoria: solo 24 bytes adicionales por elemento de datos. Sin embargo, como impulso,y la biblioteca estándar mostró una sorpresa desagradable: en el proceso, a veces requerían más memoria de la necesaria. Quizás esto se deba al equilibrio de los árboles binarios. CódigosAquí .

La biblioteca de impulso tiene spreadsort , un algoritmo que se inventó en el siglo XXI. Este es el método general más rápido disponible hoy en día en bibliotecas conocidas. Esta clasificación utiliza algunas ideas bit a bit y, al igual que esta, puede ser bastante malhumorada sobre el tipo de argumentos. Por lo general, esta clasificación muestra resultados récord, a veces significativamente mejores que los de los competidores más cercanos. La única excepción es la clasificación de las líneas C, donde es significativamente inferior a los métodos bit a bit de la biblioteca bsd. Al ordenar líneas C largas, puede ser inferior a otros métodos, por ejemplo, la clasificación por rotación o la clasificación rápida con dos puntos de anclaje. La clasificación extendida (boost v1.62) mostró un problema muy desagradable- Al ordenar pequeños (hasta 1000 elementos) arrays C-string, funciona con errores.

También hay un nuevo algoritmo pdqsort que mejora, según lo declarado por el autor, la clasificación introspectiva. Este nuevo algoritmo, que aún no se describe en Wikipedia. Sus resultados, aunque no están mal, pero no son particularmente impresionantes. Es más lento que std :: sort en enteros cortos, pero más rápido en cadenas y enteros largos. En ambos casos, la diferencia es bastante insignificante. Los mejores resultados para esta clasificación se obtuvieron para cadenas largas de C ++: aquí es inferior, aunque notablemente, solo al líder, la clasificación extendida.

En boost todavía puedes encontrar spinsort. Este también es un nuevo algoritmo que, a diferencia del anterior, tiene la propiedad de estabilidad y que aún no se describe en Wikipedia. Por lo general, está cerca del líder, pero con un notable retraso detrás de él. Requiere, aunque no demasiado, memoria adicional. Terminemos

con flat_stable_sort de la misma biblioteca de impulso. Este es otro nuevo algoritmo robusto que aún no se describe en Wikipedia. Este es, con mucho, el método más rápido, pero ligeramente inferior a la mayoría de los otros métodos de biblioteca rápida. Utiliza muy poca memoria adicional (sin embargo, siempre necesita una tabla de tamaño fijo de 8 KB) y a menudo es notablemente más rápido que el método Shell.

Considera la mesatiempo (en ms) de la operación de estos algoritmos en una computadora con 8 GB de RAM con un procesador AMD Phenom ™ II X4 955 @ 3.214 MHz. La computadora funcionó durante un total de varios meses, y el tamaño total de los datos recopilados en dos archivos json que se cargan con tablas es de casi 400 KB. Los tiempos están dados por el promedio del número de carreras; para tamaños más pequeños, estas carreras fueron más grandes. Trabajar con el caché de una manera bastante complicada cambia la velocidad de los cálculos, por lo que los resultados obtenidos son solo aproximados en el mejor de los casos (puedo suponer que las imprecisiones de tiempo pueden alcanzar hasta un 20%). Creo que en los mejores procesadores modernos para PC, el resultado puede obtenerse 2-3 veces más rápido, pero debe tenerse en cuenta que muchos procesadores más modernos funcionan al cambiar entre diferentes frecuencias y el resultado obtenido con ellos,Será aún más aproximado.

Esta y la siguiente tabla son interactivas. Además de los valores absolutos de los tiempos, también puede ver sus valores en relación con el promedio, la mediana, el mínimo y el máximo. Puedes cambiar la precisión en los personajes. También puede obtener relaciones de tiempo para diferentes tipos de rellenos y tipos de datos. Este último, por ejemplo, puede mostrar que la clasificación de cadenas C es notablemente más rápida que las cadenas C ++. Desde los métodos de clasificación, también puede seleccionar y ensamblar una variedad de subconjuntos. Por supuesto, puede establecer la clasificación por cualquier columna. Desafortunadamente, no sé cómo usar Javascript en el artículo en el centro, por lo que las tablas están disponibles solo como referencia. En el caso de que imtqy.com esté sobrecargado, también doy enlaces de respaldo a la primera y segunda tabla.

El tiempo se mide en milisegundos, pero según la ley de dependencia del tiempo, para evitar coeficientes demasiado pequeños, se dan fórmulas para microsegundos. Por lo tanto, si sustituimos el valor de N en la fórmula , entonces el resultado también debe dividirse entre 1000 para obtener un número cercano al correspondiente de la tabla. La ley de la dependencia del tiempo se deriva sobre la base de los tiempos obtenidos, de una comparación de dos resultados (generalmente se toman los extremos). Puede verificar la calidad de la ley derivada utilizando la opción de desviación relativa del valor real de la salida.

Algunas conclusiones generales de los resultados de esta tabla:

• los mejores tipos de shell en datos de hasta 10 millones de elementos pueden superar el orden e incluso algunos tipos rápidos;
• timsort está muy cerca en velocidad qsort (clib), a veces adelantando algo, y a veces viceversa;
• La ordenación en exceso y especialmente la clasificación en árboles a menudo disminuyen notablemente, pero en el contexto de una burbuja o incluso una elección, está claro que estos todavía son métodos rápidos. Curiosamente, ambos métodos a menudo tienen características muy similares: ambos construyen árboles. Es fácil notar que las dependencias para el ordenamiento dinámico y el ordenamiento arbóreo, aunque no son claramente cuadráticas, obviamente no son N log N , pero mucho peores: compárelo con la ordenación de Shell, que se comporta mucho mejor al aumentar el volumen de datos que el ordenamiento dinámico o arbóreo. que ella misma es más lenta que N log N. Por lo tanto, las implementaciones prácticas de las clasificaciones de montón y árbol no coinciden con sus especificaciones teóricas;
• los datos sobre la clasificación de cadenas muestran que las leyes de las dependencias de tiempo aquí no son las mismas que para los números: las longitudes de las cadenas que se ordenan aquí de alguna manera se superponen a estas leyes. Yo, desafortunadamente, no conozco las fórmulas para clasificaciones conocidas que darían leyes exactas de dependencias de tiempo cuando se trabaja con cadenas;
• es interesante que la velocidad de trabajar con números reales es casi la misma que los números enteros; esto es una consecuencia del hecho de que en la arquitectura moderna x86 se realizan optimizaciones muy efectivas para trabajar con la pila;
• hash_sort mostró resultados bastante mediocres, esto es posible debido al hecho de que debido al uso de memoria adicional, el rendimiento de los cachés del procesador disminuye drásticamente. En datos aleatorios pequeños (menos de cien mil elementos), la clasificación hash supera a las mejores clasificaciones rápidas. También puede notar que es posible nuevamente debido a los cachés, algunos de los resultados de esta clasificación son muy extraños, por ejemplo, los enteros 10 ⁵ , 10 ⁶ y 10 ^{7 de} 32 bits cuando se usan rellenos parcialmente ordenados se ordenan por aproximadamente el mismo tiempo! Algún tipo de efectos casi cuánticos. :) Estoy seguro de que si buscas, puedes encontrar otros resultados difíciles de explicar.

Agregaré algunas conclusiones más sobre algunos casos especiales:

• Algunos tipos de relleno de datos revelan debilidades en las clasificaciones rápidas. Sin embargo, la elección de un elemento de soporte de una manera complicada hace que la probabilidad de caer en una mala secuencia para clasificar sea prácticamente cero. También puede seleccionar un elemento de soporte en cada pase de diferentes maneras o al azar. Quizás lo hacen en qsort (clib). El método Hoare en consideración funciona muy lentamente solo en secuencias especialmente diseñadas, que se encuentran por casualidad durante el trabajo práctico; este es un caso con una probabilidad de 2 ^{N -3} / N ^N , es decir, un evento casi absolutamente imposible. Aunque si consideramos secuencias en las que el método Hoar no funciona tan lentamente como sea posible, pero solo con una desaceleración significativa, entonces hay muchos más casos de este tipo, que, sin embargo, dejan la probabilidad de que un caso de procesamiento de datos inaceptablemente lento siga siendo prácticamente insignificante, aunque muy molesto en su diferencia de cero También es casi imposible obtener accidentalmente datos sobre los cuales la clasificación rápida con dos puntos de control funcionará lentamente, de acuerdo con la ley cuadrática. Las opciones de clasificación rápida de Lomuto sin y sin un elemento de soporte muestran resultados muy pobres en casi todos los casos de llenado en particular;
• en algunos casos especiales, la clasificación de "burbujas" más lenta da excelentes resultados, y algunas de las clasificaciones más rápidas y rápidas, por el contrario, son muy malas;
• La clasificación de hash mostró un resultado muy malo en los rellenos de los tipos 8 y 9, esto se debe a que la secuencia monótona se toma de valores consecutivos, comenzando por el más pequeño, y el 1% de los números aleatorios se toma del rango del valor más bajo al máximo, lo que aburre todos los 99% consecutivos de los datos en un elemento hash. Este caso demuestra muy bien los problemas que pueden surgir al usar esta clasificación o clasificación con una matriz con datos desconocidos;
• La clasificación por selección se comporta de manera muy estable en todos los tipos de relleno, las clasificaciones en montón y en árbol también son bastante estables, sin picos ni caídas evidentes. Esto es cierto, por supuesto, para las clases de Shell, así como para la mayoría de los otros métodos rápidos de las bibliotecas estándar.

Ahora es el momento de hablar sobre los tipos de datos utilizados con los algoritmos de clasificación:

1. enteros de 32 bits con signo (int32_t), pero solo se utilizaron no negativos. También se tomaron otros datos numéricos solo no negativos; esto no reduce la generalidad de los resultados, pero hace que sea mucho más fácil obtenerlos para algunos algoritmos;
2. enteros, con signo de 64 bits (int64_t);
3. enteros, con signo de 128 bits (__int128 - compatible con al menos GCC);
4. estructuras de cinco enteros (int32_t), uno de los cuales se usa como clave (INT1P4). Al ordenar dichos datos, el número de permutaciones comienza a afectar el tiempo de cálculo de manera más significativa, por lo tanto, los métodos con menos permutaciones obtienen alguna ventaja;
5. números reales como precisión doble, doble (números flotantes);
6. cadenas cortas C ++ y C. Se tomaron cadenas de 1 a 16 (cadenas cortas y cadenas c cortas);
7. cadenas C y C ++ de longitud media, cuya longitud es de 1 a 256 (cadenas y cadenas c);
8. líneas largas C y C ++, cuya longitud es de 1 a 2 ²⁰ (esto es un poco más de un millón), y las líneas se seleccionan para que su longitud promedio no exceda de 512, por lo que las líneas se seleccionaron solo para relleno aleatorio, para otros casos, las líneas simplemente se tomaron longitudes de 1 a 512 (cadenas largas y cadenas c largas).

Y también sobre cómo llenar la matriz fuente para ordenar:

1. por casualidad
2. estrictamente ascendente (ordenado);
3. estrictamente descendente (orden inverso, inverso);
4. valores aleatorios del rango de 0 a 99 (pequeña variación, baja variación 100);
5. secuencia aleatoria de 0 y 1 (pequeña variación, baja variación 2);
6. constante 0 (extensión pequeña, baja variación 1);
7. la secuencia que lleva la versión qsort (Hoare) a la ejecución más lenta. Es curioso que existan exactamente 2 ^{N -3 de} tales secuencias entre todas las secuencias de longitud N ;
8. estrictamente ascendente, con la inserción de 1% de números aleatorios (parcialmente ordenados);
9. estrictamente descendente, con una inserción de 1% de variables aleatorias (parcialmente invertidas).

Debe enfatizarse que los datos aleatorios son el caso más típico de llenar una matriz, todos los demás métodos son extremadamente raros e incluso casi imposibles durante el funcionamiento normal de un determinado.

Veamos los resultados de la prueba, donde las clasificaciones funcionan con todas las secuencias de datos posibles. El número de tales secuencias es igual al factorial de su longitud, por lo tanto, para las secuencias de longitud 12 hay 479'001'600 variantes: una buena PC moderna calculará su número en menos de un minuto. Si tomamos secuencias de longitud 14, obtenemos ya 87'178'291'200 variantes para varias horas de funcionamiento de la computadora. Por lo tanto, la siguiente tabla muestra el tiempo promedio (en ciclos de procesador obtenidos mediante la instrucción RDTSC ) de una clasificación cuando se clasifican todas las permutaciones hasta solo 12. En los datos, se toman los tipos numéricos anteriores y las cadenas cortas. Por supuesto, uno podría notar que las secuencias con elementos repetitivos no se consideran. Sin embargo, me atrevo a sugerir que su presencia no cambiaría cualitativamente los resultados, pero podría retrasar significativamente su recepción.

Los resultados para datos tan pequeños no son muy representativos, y especialmente para métodos de clasificación complejos, pero aún complementan la idea del comportamiento de clasificación. Algunos tipos, hasta donde yo sé, reemplazan su algoritmo principal con otro cuando trabajan con matrices pequeñas: estos son tipos separados, rápidos con dos puntos de anclaje y radix_msd (los dos últimos usan insertos). Y algunas clasificaciones (flat_stable y radix) usan tablas pequeñas, pero con tamaños de datos pequeños, estas tablas resultan ser mucho más grandes que los datos en sí, lo que ralentiza en gran medida estos métodos en comparación con otros y produce resultados extraños. También se obtienen resultados extraños con otras clasificaciones bit a bit y con clasificaciones hash y array. Tales resultados inusuales se explican fácilmente por el hecho de que el tiempo de preparación de los datos antes de clasificar estos métodos para datos pequeños es más largo que el tiempo de clasificación en sí. Por supuesto, al medir intervalos de tiempo tan pequeños (nanosegundos), la influencia de varios errores en la ley mostrada es mucho mayor que en la tabla anterior. Por lo tanto, las leyes resultaron ser muy aproximadas, a menudo "con una deriva" a valores exagerados. Esto último se explica parcialmente por el hecho de que cuando se trabaja con datos pequeños, el tiempo de clasificación en sí se vuelve comparable al tiempo de invocar la función de clasificación y varias operaciones auxiliares necesarias para medir el tiempo. El programa intenta restar la sobrecarga nombrada de la salida, pero resulta que se hace más o menos aproximadamente. Con todo esto, me atrevo a suponer que al comparar los resultados para diferentes tipos de datos y tener en cuenta los comentarios realizados, a veces puede hacer suposiciones que no están muy lejos de ser precisas.

En conclusión, otra tabla que muestra cuántos métodos de prueba diferentes se requieren para ordenar memoria adicional. Obviamente, este valor depende del sistema. En mis pruebas, como ya escribí, esto es x86-64, GCC. La letra T significa el tamaño del tipo en bytes (la longitud de la cadena no está incluida en este tamaño: para las líneas C es el tamaño del puntero, para las líneas C ++ es el tamaño del descriptor, 32 bytes para x86-64 GCC), la letra L es el medio la longitud del tipo en bytes (para los números esto es T, y para las cadenas es la longitud promedio de la cadena), la letra A puede tener el valor 1 o 0: esta es la alineación con el borde de 64 bits y la letra M es la alineación del asignador de memoria estándar (se supone se alinea con un límite de 32 bytes). El símbolo ^* significa que los datos para este tipo de clasificación se obtuvieron solo sobre la base del análisis de lectura del campo VmRSS desde / proc / PID / status (el campo mencionado es el tamaño del programa de proceso).


Existen, por supuesto, otros métodos de clasificación, tanto primitivos como rápidos. La biblioteca de impulso tiene algoritmos paralelos que le permiten aprovechar la presencia de núcleos de procesador adicionales en el sistema. También puede usar el contenedor de pedido automático boost :: container :: flat_multiset en lugar de std :: multiset, pero funciona muy lentamente.

Aprovecho esta oportunidad para decir algunos comentarios sobre la biblioteca de impulso en general. Recomiendo no pasar de largo. Incluso las características que están en la biblioteca estándar en boost, como regla, se implementan mejor y, a veces (como las expresiones regulares, por ejemplo) son mucho mejores. Si hablamos de contenedores, entonces en boost son notablemente más grandes, y los que coinciden con los estándar son a veces algo más rápidos y a menudo tienen mejoras pequeñas, pero agradables. Boost comprueba los tipos más a fondo, lo que a veces puede ayudar a detectar errores casi evasivos que generalmente no se manifiestan, pero en algunas circunstancias pueden activarse inesperadamente. Las desventajas de boost incluyen mensajes incondicionalmente completamente ilegibles y de gran volumen sobre errores de compilación en muchas construcciones de esta biblioteca; esto, aunque en menor medida, se aplica a la biblioteca estándar. Es hora de que los desarrolladores de C ++ hagan algo al respecto.

Todos los archivos con pruebas y algunos otros materiales relacionados se pueden tomar de mi repositorio . Si alguien está interesado en los datos de origen sin procesar, puede obtenerlos aquí (1,4 MB). Estaré encantado de cualquier comentario, crítica y adiciones.