Timsort: el algoritmo de clasificación más rápido del que nunca has oído hablar

brandon2018/06/26

Timsort: un algoritmo de ordenación muy rápido, O(n log n), estable creado para el mundo real — no construido en la academia.

People Mentioned

Companies Mentioned

featured image - Timsort: el algoritmo de clasificación más rápido del que nunca has oído hablar

Foto de Marc Sendra martorell en Unsplash

Timsort: un algoritmo de clasificación muy rápido, O (n log n), estable creado para el mundo real, no construido en la academia.

Haga clic aquí para ver el artículo actualizado:

Timsort: el algoritmo de clasificación más rápido del que nunca ha oído hablar _Timsort: un algoritmo de clasificación muy rápido, O (n log n), estable creado para el mundo real, no construido en la academia... _skerritt.blog

Imagen de Tim Peter de aquí

Timsort es un algoritmo de clasificación que es eficiente para datos del mundo real y no creado en un laboratorio académico. Tim Peters creó Timsort para el lenguaje de programación Python en 2001. Timsort primero analiza la lista que intenta ordenar y luego elige un enfoque basado en el análisis de la lista.

Desde que se inventó el algoritmo, se ha utilizado como el algoritmo de clasificación predeterminado en Python, Java , la plataforma Android y en GNU Octave.

La notación O grande de Timsort es O(n log n). Para aprender sobre la notación Big O, lea esto .

desde aquí

El tiempo de clasificación de Timsort es el mismo que el de Mergesort, que es más rápido que la mayoría de los otros tipos que pueda conocer. Timsort en realidad utiliza la ordenación por inserción y la ordenación por combinación, como verá pronto.

Peters diseñó Timsort para usar elementos ya ordenados que existen en la mayoría de los conjuntos de datos del mundo real. A estos elementos ya ordenados los llama “ejecuciones naturales”. Itera sobre los datos recopilando los elementos en ejecuciones y fusionando simultáneamente esas ejecuciones en una sola.

La matriz tiene menos de 64 elementos.

Si la matriz que intentamos ordenar tiene menos de 64 elementos, Timsort ejecutará una ordenación por inserción.

Una ordenación por inserción es una ordenación simple que es más efectiva en listas pequeñas. Es bastante lento en listas más grandes, pero muy rápido en listas pequeñas. La idea de una ordenación por inserción es la siguiente:

Mira los elementos uno por uno
Cree una lista ordenada insertando el elemento en la ubicación correcta

Aquí hay una tabla de seguimiento que muestra cómo la ordenación por inserción ordenaría la lista [34, 10, 64, 51, 32, 21]

Imagen tomada por mí, de mi sitio web skerritt.tech

En este caso, estamos insertando los elementos recién ordenados en un nuevo subconjunto, que comienza al principio del conjunto.

Aquí hay un gif que muestra la ordenación por inserción:

Tomado de aquí

Más sobre carreras

Si la lista tiene más de 64 elementos, el algoritmo realizará una primera pasada por la lista en busca de partes que sean estrictamente crecientes o decrecientes. Si la parte es decreciente, invertirá esa parte.

Entonces, si la ejecución está disminuyendo, se verá así (donde la ejecución está en negrita):

Imagen de mi sitio web, skerritt.tech

Si no disminuye, se verá así:

Imagen de mi sitio web, skerritt.tech

El minrun es un tamaño que se determina en función del tamaño de la matriz. El algoritmo lo selecciona de modo que la mayoría de las ejecuciones en una matriz aleatoria tengan, o se conviertan en minrun, en longitud. Fusionar 2 matrices es más eficiente cuando el número de ejecuciones es igual o ligeramente menor que una potencia de dos. Timsort elige minrun para tratar de garantizar esta eficiencia, asegurándose de que minrun sea igual o menor que una potencia de dos.

El algoritmo elige minrun del rango de 32 a 64 inclusive. Elige minrun de modo que la longitud de la matriz original, cuando se divide por minrun, sea igual o ligeramente menor que una potencia de dos.

Si la longitud de la carrera es menor que minrun, calcula la longitud de esa carrera lejos de minrun. Con este nuevo número, toma esa cantidad de elementos antes de la ejecución y realiza una ordenación por inserción para crear una nueva ejecución.

Entonces, si minrun es 63 y la duración de la ejecución es 33, haces 63–33 = 30. Luego tomas 30 elementos del frente del final de la ejecución, por lo que son 30 elementos de run[33] y luego realizas una ordenación por inserción para crear una nueva ejecución.

Una vez completada esta parte, ahora deberíamos tener un montón de ejecuciones ordenadas en una lista.

fusión

Gif de Giphy

Timsort ahora realiza mergesort para fusionar las ejecuciones. Sin embargo, Timsort se asegura de mantener la estabilidad y el equilibrio de fusión durante la clasificación por fusión.

Para mantener la estabilidad no debemos intercambiar 2 números de igual valor. Esto no solo mantiene sus posiciones originales en la lista, sino que permite que el algoritmo sea más rápido. En breve discutiremos el balance de fusión.

A medida que Timsort encuentra ejecuciones, las agrega a una pila. Una pila simple se vería así:

Imagen de mi sitio web, skerritt.tech

Imagina una pila de platos. No puedes tomar platos de abajo, así que tienes que tomarlos de arriba. Lo mismo es cierto acerca de una pila.

Timsort intenta equilibrar dos necesidades en competencia cuando se ejecuta mergesort. Por un lado, nos gustaría retrasar la fusión tanto como sea posible para explotar patrones que puedan surgir más adelante. Pero nos gustaría aún más hacer la fusión lo antes posible para aprovechar la ejecución que la ejecución que acaba de encontrar todavía está alta en la jerarquía de la memoria. Tampoco podemos retrasar la fusión "demasiado tiempo" porque consume memoria para recordar las ejecuciones que aún no están fusionadas, y la pila tiene un tamaño fijo.

Para asegurarse de que tengamos este compromiso, Timsort realiza un seguimiento de los tres elementos más recientes de la pila y crea dos leyes que deben ser válidas para esos elementos:

1. A > B + C

2. B > C

Donde A, B y C son los tres elementos más recientes de la pila.

En palabras del propio Tim Peters:

Lo que resultó ser un buen compromiso mantiene dos invariantes en las entradas de la pila, donde A, B y C son las longitudes de los tres segmentos más a la derecha que aún no se han fusionado.

Por lo general, la fusión de tramos adyacentes de diferentes longitudes en su lugar es difícil. Lo que lo hace aún más difícil es que tenemos que mantener la estabilidad. Para evitar esto, Timsort reserva memoria temporal. Coloca la más pequeña (llamando tanto a las ejecuciones A como a la B) de las dos ejecuciones en esa memoria temporal.

Galopando

Gif de Giphy

Mientras Timsort está fusionando A y B, se da cuenta de que una ejecución ha sido "ganadora" muchas veces seguidas. Si resulta que la serie A consiste en números completamente más pequeños que la serie B, entonces la serie A terminaría en su lugar original. Fusionar las dos ejecuciones implicaría mucho trabajo para lograr nada.

La mayoría de las veces, los datos tendrán alguna estructura interna preexistente. Timsort asume que si muchos valores de la ejecución A son más bajos que los valores de la ejecución B, entonces es probable que A continúe teniendo valores más pequeños que B.

Imagen de mi sitio web, skerritt.tech . Imagen de 2 ejecuciones de ejemplo, A y B. Las ejecuciones deben ser estrictamente crecientes o decrecientes, por lo que se eligieron estos números.

Timsort entrará entonces en modo de galope. En lugar de comparar A[0] y B[0] entre sí, Timsort realiza una búsqueda binaria de la posición adecuada de b[0] en a[0]. De esta forma, Timsort puede mover una sección completa de A a su lugar. Luego, Timsort busca la ubicación adecuada de A[0] en B. Timsort luego moverá una sección completa de la lata B a la vez y la colocará en su lugar.

Veamos esto en acción. Timsort comprueba B[0] (que es 5) y mediante una búsqueda binaria busca la ubicación correcta en A.

Bueno, B[0] pertenece al final de la lista de A. Ahora Timsort busca A[0] (que es 1) en la ubicación correcta de B. Así que estamos buscando a dónde va el número 1. Este número va al comienzo de B. Ahora sabemos que B pertenece al final de A y A pertenece al comienzo de B.

Resulta que esta operación no vale la pena si la ubicación adecuada para B[0] está muy cerca del comienzo de A (o viceversa). por lo tanto, el modo de galope sale rápidamente si no está dando sus frutos. Además, Timsort toma nota y hace que sea más difícil ingresar al modo de galope más tarde al aumentar la cantidad de victorias consecutivas solo A o solo B requeridas para ingresar. Si el modo de galope está dando sus frutos, Timsort facilita el reingreso.

En resumen, Timsort hace 2 cosas increíblemente bien:

Gran rendimiento en arreglos con estructura interna preexistente
Ser capaz de mantener una especie estable

Anteriormente, para lograr una ordenación estable, tenía que comprimir los elementos de su lista con números enteros y ordenarlos como una matriz de tuplas.

Código

Si no está interesado en el código, no dude en omitir esta parte. Hay más información debajo de esta sección.

El código fuente a continuación se basa en el trabajo mío y de Nanda Javarma. El código fuente no está completo, ni es similar al código fuente ordenado() oficial de Python. Este es solo un Timsort simplificado que implementé para tener una idea general de Timsort. Si quieres ver el código fuente original de Timsort en todo su esplendor, échale un vistazo aquí . Timsort se implementa oficialmente en C, no en Python.

Timsort en realidad está integrado en Python, por lo que este código solo sirve como explicación. Para usar Timsort simplemente escriba:

lista.ordenar()

ordenado (lista)

Si desea dominar cómo funciona Timsort y familiarizarse con él, ¡le sugiero que intente implementarlo usted mismo!

Este artículo se basa en la introducción original de Tim Peters a Timsort, que se encuentra aquí .