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 , [4] en la plataforma Android , [5] en GNU Octave , [6] en V8 , [7] Swift , [8] y Rust . [9]
Clase | Algoritmo de clasificación |
---|---|
Estructura de datos | Formación |
Rendimiento en el peor de los casos | [1] [2] |
Rendimiento en el mejor de los casos | [3] |
Rendimiento medio | |
Complejidad espacial en el peor de los casos |
Utiliza técnicas del artículo de 1993 de Peter McIlroy "Clasificación optimista y complejidad teórica de la información". [10]
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
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 ejecuciones no consecutivas, puede haber un elemento con la misma clave de elementos dentro de las ejecuciones y 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:
- | Z | > | Y | + | X |
- | Y | > | X | [11]
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. [12] Estos invariantes mantienen las fusiones aproximadamente equilibradas mientras mantienen un compromiso entre retrasar la fusión para equilibrar, explotar 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
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
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 ejecuciones.
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. [13]
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
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 de una potencia de dos, Timsort elige minrun para tratar de garantizar la condición anterior. [11]
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. [11]
Análisis
En el peor de los casos , Timsort tomacomparaciones 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 . [3]
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. [14]
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 64 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. [14] Utilizando 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. [15]
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 26 ). (Las versiones anteriores de Android ya activaron esta excepción para ciertas entradas de tamaño65 536 (2 16 ))
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 [16] y Android.
Referencias
- ^ Peters, Tim. "Clasificación [Python-Dev]" . Lista de distribución de desarrolladores de Python . Consultado el 24 de febrero de 2011 .
[Timsort] también tiene aspectos positivos: es estable (los elementos que se comparan iguales conservan su orden relativo, por lo que, por ejemplo, si ordena primero por código postal y una segunda vez por nombre, las personas con el mismo nombre seguirán apareciendo en orden creciente código postal; esto es importante en aplicaciones que, por ejemplo, refinan los resultados de las consultas en función de la entrada del usuario). ... No tiene casos malos (O (N log N) es el peor de los casos; N − 1 compara es el mejor).
- ^ "[GOTAS]" . Consultado el 1 de septiembre de 2018 .
TimSort es un algoritmo de clasificación intrigante diseñado en 2002 para Python, cuya complejidad en el peor de los casos se anunció, pero no se demostró hasta nuestra reciente preimpresión.
- ^ a b Chandramouli, Badrish; Goldstein, Jonathan (2014). La paciencia es una virtud: revisando la fusión y la clasificación en los procesadores modernos . SIGMOD / PODS.
- ^ "[# JDK-6804124] (coll) Reemplace" mergesort modificado "en java.util.Arrays.sort por timsort" . Sistema de errores JDK . Consultado el 11 de junio de 2014 .
- ^ "Clase: java.util.TimSort " . Documentación de Android Gingerbread . Archivado desde el original el 16 de julio de 2015 . Consultado el 24 de febrero de 2011 .
- ^ "liboctave / util / oct-sort.cc" . Repositorio Mercurial del código fuente de Octave . Líneas 23-25 del bloque de comentarios inicial . Consultado el 18 de febrero de 2013 .
Código robado en gran parte de listobject.c de Python, que en sí mismo no tenía encabezado de licencia. Sin embargo, gracias a Tim Peters por las partes del código que estafé.
- ^ "Ordenar las cosas en V8 · V8" . v8.dev . Consultado el 21 de diciembre de 2018 .
- ^ "¿Es estable sort () en Swift 5?" . Foros rápidos . 4 de julio de 2019 . Consultado el 4 de julio de 2019 .
- ^ "rebanada - óxido" . doc.rust-lang.org . Consultado el 17 de septiembre de 2020 .
- ^ McIlroy, Peter (enero de 1993). "Complejidad teórica de la información y ordenación optimista". Actas del Cuarto Simposio Anual ACM-SIAM sobre Algoritmos Discretos . págs. 467–474. ISBN 0-89871-313-7.
- ^ a b c "listsort.txt" . Código fuente de Python . 10 de febrero de 2017.
- ^ MacIver, David R. (11 de enero de 2010). "Comprender la ordenación de tiempos, parte 1: ordenación adaptativa" . Consultado el 5 de diciembre de 2015 .
- ^ Peters, Tim. "listsort.txt" . Repositorio CPython git . Consultado el 5 de diciembre de 2019 .
- ^ a b de Gouw, Stijn; Rot, Jurriaan; de Boer, Frank S .; Bubel, Richard; Hähnle, Reiner (julio de 2015). "Java.utils.Collection.sort () de OpenJDK no funciona: lo bueno, lo malo y lo peor" (PDF) . Verificación asistida por computadora : 273–289. doi : 10.1007 / 978-3-319-21690-4_16 .
- ^ de Gouw, Stijn (24 de febrero de 2015). "Demostrar que el algoritmo de clasificación de Android, Java y Python está roto (y mostrar cómo solucionarlo)" . Consultado el 6 de mayo de 2017 .
- ^ Rastreador de problemas de Python - Problema 23515: Mala lógica en merge_collapse de timsort
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