Timsort - Timsort

Timsort

Clase	Algoritmo de clasificación
Estructura de datos	Formación
Rendimiento en el peor de los casos	${\ Displaystyle O (n \ log n)}$
Rendimiento en el mejor de los casos	${\ Displaystyle O (n)}$
Rendimiento medio	${\ Displaystyle O (n \ log n)}$
Complejidad espacial en el peor de los casos	${\ Displaystyle O (n)}$

Timsort es un algoritmo de clasificación estable híbrido , derivado de la clasificación por combinación y la clasificación por inserción , diseñado para funcionar bien en muchos tipos de datos del mundo real. Fue implementado por Tim Peters en 2002 para su uso en el lenguaje de programación Python . El algoritmo encuentra subsecuencias de los datos que ya están ordenados (ejecutados) y los usa para ordenar el resto de manera más eficiente. Esto se hace fusionando ejecuciones hasta que se cumplan ciertos criterios. Timsort ha sido el algoritmo de clasificación estándar de Python desde la versión 2.3. También se utiliza para ordenar matrices de tipo no primitivo en Java SE 7 , en la plataforma Android , en GNU Octave , en V8 , Swift y Rust .

Utiliza técnicas del artículo de 1993 de Peter McIlroy "Clasificación optimista y complejidad teórica de la información".

Operación

Timsort fue diseñado para aprovechar las ejecuciones de elementos ordenados consecutivos que ya existen en la mayoría de los datos del mundo real, ejecuciones naturales . Repite los elementos de recopilación de datos en ejecuciones y, al mismo tiempo, coloca esas ejecuciones en una pila. Siempre que las ejecuciones en la parte superior de la pila coincidan con un criterio de combinación , se combinan. Esto continúa hasta que se atraviesan todos los datos; luego, todas las ejecuciones se fusionan de dos en dos y solo queda una ejecución ordenada. La ventaja de fusionar ejecuciones ordenadas en lugar de fusionar sublistas de tamaño fijo (como se hace con la clasificación por fusión tradicional) es que disminuye el número total de comparaciones necesarias para ordenar la lista completa.

Cada ejecución tiene un tamaño mínimo, que se basa en el tamaño de la entrada y se define al inicio del algoritmo. Si una ejecución es más pequeña que este tamaño de ejecución mínimo, la ordenación por inserción se utiliza para agregar más elementos a la ejecución hasta que se alcanza el tamaño mínimo de ejecución.

Combinar criterios

Las corridas se insertan en una pila . Si | Z | ≤ | Y | + | X | , luego X e Y se fusionan y se reemplazan en la pila. De esta forma, la fusión continúa hasta que todas las ejecuciones satisfagan i. | Z | > | Y | + | X | y ii. | Y | > | X | .

Timsort es un algoritmo de clasificación estable (se mantiene el orden de los elementos con la misma clave) y se esfuerza por realizar fusiones equilibradas (una fusión, por lo tanto, fusiona ejecuciones de tamaños similares).

Para lograr la estabilidad de clasificación, solo se combinan las ejecuciones consecutivas. Entre dos corridas no consecutivas, puede haber un elemento con la misma clave dentro de las corridas. La fusión de esas dos ejecuciones cambiaría el orden de claves iguales. Ejemplo de esta situación ([] son ​​ejecuciones ordenadas): [1 2 2] 1 4 2 [0 1 2]

En la búsqueda de fusiones equilibradas, Timsort considera tres carreras en la parte superior de la pila, X , Y , Z , y mantiene las invariantes:

Si se viola alguno de estos invariantes, Y se fusiona con el menor de X o Z y los invariantes se comprueban nuevamente. Una vez que se mantienen los invariantes, puede comenzar la búsqueda de una nueva ejecución en los datos. Estos invariantes mantienen las fusiones como aproximadamente equilibradas mientras mantienen un compromiso entre retrasar la fusión para mantener el equilibrio, aprovechar la aparición de ejecuciones recientes en la memoria caché y hacer que las decisiones de fusión sean relativamente simples.

Fusionar la sobrecarga del espacio

Para fusionar, Timsort copia los elementos de la matriz más pequeña (X en esta ilustración) en la memoria temporal, luego ordena y llena los elementos en el orden final en el espacio combinado de X e Y.

La implementación de ordenación de combinación original no está en su lugar y tiene una sobrecarga de espacio de N (tamaño de datos). Existen implementaciones de ordenación por combinación in situ, pero tienen una sobrecarga de tiempo elevada. Para lograr un término medio, Timsort realiza una clasificación de combinación con una sobrecarga de tiempo pequeña y una sobrecarga de espacio más pequeña que N.

Primero, Timsort realiza una búsqueda binaria para encontrar la ubicación donde se insertaría el primer elemento de la segunda ejecución en la primera ejecución ordenada, manteniéndolo ordenado. Luego, realiza el mismo algoritmo para encontrar la ubicación donde se insertaría el último elemento de la primera ejecución en la segunda ejecución ordenada, manteniéndolo ordenado. Los elementos antes y después de estas ubicaciones ya están en su lugar correcto y no es necesario fusionarlos. Luego, el menor de los elementos restantes de las dos ejecuciones se copia en la memoria temporal y los elementos se fusionan con la ejecución más grande en el espacio ahora libre. Si la primera ejecución es más pequeña, la combinación comienza desde el principio; si el segundo es más pequeño, la fusión comienza al final. Esta optimización reduce el número de movimientos de elementos requeridos, el tiempo de ejecución y la sobrecarga de espacio temporal en el caso general.

Ejemplo: dos ejecuciones [1, 2, 3, 6, 10] y [4, 5, 7, 9, 12, 14, 17] deben fusionarse. Tenga en cuenta que ambas ejecuciones ya están ordenadas individualmente. El elemento más pequeño de la segunda ejecución es 4 y tendría que agregarse en la cuarta posición de la primera ejecución para preservar su orden (asumiendo que la primera posición de una ejecución es 1). El elemento más grande de la primera ejecución es 10 y debería agregarse en la quinta posición de la segunda ejecución para preservar su orden. Por tanto, [1, 2, 3] y [12, 14, 17] ya se encuentran en sus posiciones finales y las corridas en las que se requieren movimientos de elementos son [6, 10] y [4, 5, 7, 9]. Con este conocimiento, solo necesitamos asignar un búfer temporal de tamaño 2 en lugar de 5.

Fusionar dirección

La fusión se puede realizar en ambas direcciones: de izquierda a derecha, como en el método de fusión tradicional, o de derecha a izquierda.

Modo galopante durante la fusión

Los elementos (señalados con una flecha azul) se comparan y el elemento más pequeño se mueve a su posición final (señalado con una flecha roja).

Una combinación individual de las ejecuciones R1 y R2 mantiene el recuento de elementos consecutivos seleccionados de una ejecución. Cuando este número alcanza el umbral de galope mínimo ( min_gallop ), Timsort considera que es probable que aún se puedan seleccionar muchos elementos consecutivos de esa carrera y cambia al modo de galope. Supongamos que R1 es responsable de activarlo. En este modo, el algoritmo realiza una búsqueda exponencial , también conocida como búsqueda galopante, para el siguiente elemento x de la ejecución R2 en la ejecución R1. Esto se hace en dos etapas: la primera encuentra el rango (2 ^k - 1, 2 ^{k + 1} - 1) donde x es. La segunda etapa realiza una búsqueda binaria del elemento x en el rango encontrado en la primera etapa. El modo galopante es un intento de adaptar el algoritmo de fusión al patrón de intervalos entre elementos en las ejecuciones.

Todos los elementos rojos son más pequeños que el azul (aquí, 21). Por lo tanto, se pueden mover en un fragmento a la matriz final.

Galopar no siempre es eficaz. En algunos casos, el modo galopante requiere más comparaciones que una simple búsqueda lineal . Según los puntos de referencia realizados por el desarrollador, galopar es beneficioso solo cuando el elemento inicial de una ejecución no es uno de los primeros siete elementos de la otra ejecución. Esto implica un umbral inicial de 7. Para evitar los inconvenientes del modo de galope, se toman dos acciones: (1) Cuando se encuentra que el galope es menos eficiente que la búsqueda binaria , se sale del modo de galope. (2) El éxito o el fracaso del galope se utiliza para ajustar min_gallop . Si el elemento seleccionado es de la misma matriz que devolvió un elemento anteriormente, min_gallop se reduce en uno, lo que fomenta el regreso al modo galopante. De lo contrario, el valor se incrementa en uno, desalentando así un regreso al modo galopante. En el caso de datos aleatorios, el valor de min_gallop se vuelve tan grande que el modo de galope nunca se repite.

Carreras descendentes

Para aprovechar también los datos clasificados en orden descendente, Timsort invierte las ejecuciones estrictamente descendentes cuando las encuentra y las agrega a la pila de ejecuciones. Dado que las ejecuciones descendentes se invierten posteriormente a ciegas, la exclusión de ejecuciones con elementos iguales mantiene la estabilidad del algoritmo; es decir, los elementos iguales no se revertirán.

Tamaño mínimo de ejecución

El algoritmo Timsort busca secuencias ordenadas de tamaño mínimo, minruns, para realizar su ordenación.

Debido a que la fusión es más eficiente cuando el número de corridas es igual o ligeramente menor que una potencia de dos, y notablemente menos eficiente cuando el número de corridas es un poco más que una potencia de dos, Timsort elige minrun para tratar de garantizar la condición anterior.

Minrun se elige en el rango de 32 a 64 inclusive, de modo que el tamaño de los datos, dividido por minrun , sea igual o ligeramente menor que una potencia de dos. El algoritmo final toma los seis bits más significativos del tamaño de la matriz, agrega uno si se establece alguno de los bits restantes y usa ese resultado como minrun . Este algoritmo funciona para todos los arreglos, incluidos los menores de 64; para matrices de tamaño 63 o menos, esto establece minrun igual al tamaño de matriz y Timsort se reduce a una ordenación de inserción.

Análisis

En el peor de los casos , Timsort realiza comparaciones para ordenar una matriz de n elementos. En el mejor de los casos, que ocurre cuando la entrada ya está ordenada, se ejecuta en tiempo lineal, lo que significa que es un algoritmo de ordenación adaptativo . ${\ Displaystyle O (n \ log n)}$

Es ventajoso sobre Quicksort para ordenar referencias de objetos o punteros porque estos requieren una costosa dirección indirecta de la memoria para acceder a los datos y realizar comparaciones y los beneficios de coherencia de la caché de Quicksort se reducen en gran medida.

Verificación formal

En 2015, investigadores holandeses y alemanes del proyecto EU FP7 ENVISAGE encontraron un error en la implementación estándar de Timsort.

Específicamente, las invariantes en los tamaños de ejecución apilada aseguran un límite superior ajustado en el tamaño máximo de la pila requerida. La implementación preasignó una pila suficiente para clasificar 2 ⁶⁴ bytes de entrada y evitó más comprobaciones de desbordamiento.

Sin embargo, la garantía requiere que los invariantes se apliquen a cada grupo de tres ejecuciones consecutivas, pero la implementación solo lo verificó para los tres primeros. Usando la herramienta KeY para la verificación formal del software Java, los investigadores encontraron que esta verificación no es suficiente, y pudieron encontrar longitudes de ejecución (y entradas que generaron esas longitudes de ejecución) que resultarían en una violación más profunda de las invariantes en la pila. después de que se fusionó la parte superior de la pila.

Como consecuencia, para ciertas entradas, el tamaño asignado no es suficiente para contener todas las ejecuciones no fusionadas. En Java, esto genera para esas entradas una excepción de matriz fuera del límite. La entrada más pequeña que activa esta excepción en Java y Android v7 es de tamaño67 108 864 (2 ²⁶ ). (Las versiones anteriores de Android ya activaron esta excepción para ciertas entradas de tamaño65 536 (2 ¹⁶ ))

La implementación de Java se corrigió aumentando el tamaño de la pila preasignada en función de un análisis actualizado del peor de los casos. El artículo también mostró por métodos formales cómo establecer el invariante pretendido comprobando que las cuatro corridas superiores de la pila satisfacen las dos reglas anteriores. Este enfoque fue adoptado por Python y Android.

Referencias

Otras lecturas

• Auger, Nicolas; Nicaud, Cyril; Pivoteau, Carine (2015). "Combinar estrategias: de Merge Sort a TimSort" . hal-01212839 .
• Auger, Jugé, Nicaud, Pivoteau (2018). "Sobre la complejidad del peor de los casos de TimSort" . ESA 2018.
• Sam Buss, Alexander Knop. "Estrategias para una clasificación de combinación estable". SODA 2019.

enlaces externos

• timsort.txt - explicación original de Tim Peters