Grokking Timsort

Question

Há um (relativamente) novo tipo no bloco chamado TimSort. Tem sido usado como lista de python.sort e agora vai ser A nova matriz.sort em Java 7.

Há alguma documentação e a pequeno artigo da Wikipedia Descrevendo as propriedades de alto nível do tipo e algumas avaliações de desempenho de baixo nível, mas fiquei curioso se alguém pode fornecer algum pseudocódigo para ilustrar o que Timsort está fazendo exatamente e quais são as principais coisas que o tornam zippy. (Es. Com relação ao artigo citado, "Atenção e a complexidade teórica da classificação e da informação". ")

(Veja também Postagem de Stackoverflow relacionada.)

Answer 1

Citando a parte relevante de uma postagem de blog agora excluída: Visualizando algoritmos de classificação: Timsort de Python

O fim dos negócios do TIMSORT é um mesclado que opera em corridas de elementos pré-classificados. Um Minrun de comprimento mínimo de execução é escolhido para garantir que as mescladas finais sejam o mais equilibradas possível - para 64 elementos, o Minrun é 32. Antes do início das mescladas, um único passe é feito através dos dados para detectar execuções pré -existentes de classificação classificadas elementos. As corridas descendentes são tratadas simplesmente revertendo -as no lugar. Se o comprimento resultante da execução for menor que o MinRun, ele será impulsionado para o MinRun usando o tipo de inserção. Em uma matriz embaralhada, sem execuções pré-existentes significativas, esse processo se parece exatamente com o nosso palpite acima: blocos de pré-classificação de elementos MinRun usando o tipo de inserção, antes de se fundir com a classificação de mesclagem.

[...]

• Timsort encontra uma corrida descendente e reverte a corrida no local. Isso é feito diretamente na variedade de ponteiros, então parece "instantâneo" do nosso ponto de vista.
• A execução agora é impulsionada para o comprimento Minrun usando o tipo de inserção.
• Nenhuma execução é detectada no início do próximo bloco e a classificação da inserção é usada para classificar o bloco inteiro. Observe que os elementos classificados na parte inferior deste bloco não são tratados especialmente - o Timsort não detecta execuções que começam no meio dos blocos sendo impulsionados para o MinRun.
• Finalmente, o Mergesort é usado para mesclar as corridas.

Answer 2

Essa mudança passou pelo Lista de discussão do núcleo-libs Quando entrou, há alguma discussão e links úteis lá. Aqui está o Web Rev com alterações de revisão de código e também o Patch original.

Os comentários no código dizem:

Implementação Nota: Esta implementação é um estável, adaptável,
Mergesort iterativo que requer muito menos de N LG (n) comparações
Quando a matriz de entrada é parcialmente classificada, enquanto oferece o
o desempenho de um mescle tradicional quando a matriz de entrada é
ordenado aleatoriamente. Se a matriz de entrada estiver quase classificada, o
A implementação requer aproximadamente n comparações.
Os requisitos de armazenamento temporários variam de uma pequena constante para quase classificados
Matrizes de entrada para N/2 Referências de objeto para entrada ordenada aleatoriamente
matrizes.

A implementação aproveita a mesma vantagem da ascensão e
ordem decrescente em sua matriz de entrada e pode aproveitar
ordem ascendente e decrescente em diferentes partes do mesmo
Array de entrada. É adequado para fusão de duas ou mais matrizes classificadas:
Simplesmente concatenar as matrizes e classificar a matriz resultante.
A implementação foi adaptada da lista de Tim Peters para Python
Timsort. Ele usa técnicos de "otimista de Peter McIlroy
A complexidade teórica de classificação e informação ", em Anais do
Quarto Simpósio ACM-Siam Anual sobre Algoritmos Discretos, pp 467-474,
Janeiro de 1993.

Enterrado lá está o Link muito útil para os detalhes da implementação do Python, e acho que é um ótimo lugar para começar, seguido pelo código. Para ser incrivelmente alto, o TIMSORT melhora o desempenho percebendo execuções de dados classificados e aproveitando essa estrutura durante o tipo.