Grokking Timsort

Question

Hay una (relativamente) nueva especie en el bloque llamado Timsort. Ha sido utilizado como list.sort de Python, y ahora va a ser el nuevo Array.sort en Java 7 .

Hay algunos documentación y un pequeño artículo de Wikipedia describir las propiedades de alto nivel de la clase y algunas evaluaciones de desempeño de bajo nivel, pero tenía curiosidad si alguien puede proporcionar algún pseudocódigo para ilustrar lo que Timsort está haciendo, exactamente, y cuáles son las principales cosas que hacen que sea enérgico. (Esp. Con respecto al documento citado, "Optimista Clasificación e Información teórico complejidad".)

(Véase también relacionada href="https://stackoverflow.com/questions/154504/is-timsort-general-purpose-or-python-specific"> .)

Answer 1

Citando la parte pertinente de una entrada en el blog ahora eliminado: Visualizando algoritmos de ordenación de Python: timsort

  

El negocio de fin de timsort es un mergesort que funciona en las carreras de elementos pre-ordenados. Un minrun mínimo de longitud de ejecución se elige para asegurarse de que las fusiones finales son lo más equilibrada posible - de 64 elementos, minrun pasa a ser 32. Antes de las fusiones comienzan, de una sola pasada se hizo a través de los datos para detectar carreras de pre-existentes de los ordenados elementos. carreras descendente se manejan simplemente invirtiendo en su lugar. Si la longitud de ejecución resultante es menor que minrun, que se ha elevado a minrun usando la ordenación por inserción. En una matriz de barajado con ninguna carrera preexistentes significativas, este proceso se ve exactamente como nuestra suposición anterior: bloques de elementos minrun clasificación previa mediante la ordenación por inserción, antes de fusionarse con la combinación de tipo

.

[...]

• timsort encuentra una carrera descendente, e invierte la carrera en el lugar. Esto se realiza directamente en la matriz de punteros, por lo que parece "instantánea" de nuestro punto de vista.
• La carrera está ahora impulsado a la longitud minrun usando la ordenación por inserción.
• Ninguna carrera se detecta al comienzo del siguiente bloque, y el tipo de inserción se utiliza para ordenar todo el bloque. Tenga en cuenta que los elementos ordenados en la parte inferior de este bloque no se tratan de forma especial -. Timsort no detecta carreras que se inician en el medio de bloques que se ha elevado a minrun
• Por último, mergesort se utiliza para fusionar las carreras.

Answer 2

Este cambio fue a través de los núcleo-libs lista de correo cuando entró en lo que existe cierta discusión y enlaces útiles allí. Aquí están los href="http://cr.openjdk.java.net/~martin/webrevs/openjdk7/timsort/" rel="nofollow noreferrer"> rev red original de parche .

Los comentarios en el código dicen:

  

Nota de implementación: Esta aplicación es un producto estable, adaptable, España    mergesort iterativo que requiere mucho menos que n lg (n) comparaciones
   cuando la matriz de entrada se ordena parcialmente, al tiempo que ofrece la Red    el rendimiento de un mergesort tradicionales cuando la matriz de entrada es
   ordenado al azar. Si la matriz de entrada está a punto de ordenadas, la Red    aplicación requiere aproximadamente n comparaciones.
   los requisitos de almacenamiento temporales varían de una pequeña constante durante casi ordenada
   matrices de entrada a n / 2 referencias de objetos para la entrada ordenada aleatoriamente
   matrices.

     

La aplicación tiene la misma ventaja de ascenso y
   orden descendente en su matriz de entrada, y puede tomar ventaja de
   orden ascendente y descendente en diferentes partes del mismo
   matriz de entrada. Se adapta bien a la fusión de dos o más matrices clasificadas:
   simplemente concatenar las matrices y ordenar la matriz resultante.
   La aplicación es una adaptación de la lista de Tim Peters tipo para Python
    TimSort . Utiliza Techiques de "Optimista
de Peter McIlroy    La clasificación y la información teórica Complejidad", en Actas de la Red    Cuarta Anual ACM-SIAM Simposio sobre algoritmos discretos, pp 467-474, España    De enero de 1993.

enterrado en existe la enlace muy útil para los detalles de implementación de Python , y yo creo que es un gran lugar para comenzar, seguido por el código. Para ser increíblemente alto nivel al respecto, timsort mejora el rendimiento al darse cuenta de carreras de datos ordenados y aprovechando que la estructura durante la clase.