O Timsort é específico para o uso geral ou o Python?

Question

O Timsort é um mesclado natural, estável e natural. Possui desempenho sobrenatural em muitos tipos de matrizes parcialmente ordenadas (menos que LG (N!) Precisadas comparações e poucas como N-1), mas tão rápido quanto o híbrido de amostras altamente sintonizadas do Python em matrizes aleatórias.

Você viu timsort usado fora do Cpython? Isso faz sentido?

Answer 1

Sim, faz um pouco de sentido usar Timsort fora do CPython, em específico, ou python, em geral.

Atualmente há um esforço em andamento Para substituir a "classificação de mesclagem modificada" de Java pelo TIMSORT, e os resultados iniciais são bastante positivos.

Answer 2

O algoritmo é bastante genérico, mas os benefícios são bastante específicos do Python. Ao contrário da maioria das rotinas de classificação, o que a lista de Python. muito Mais caro do que trocar itens (que sempre é apenas um conjunto de cópias de ponteiro) ou até alocando alguma memória extra (porque é sempre apenas uma variedade de indicadores, e a sobrecarga é pequena em comparação com a sobrecarga média em qualquer operação do Python.)

Se você estiver sob restrições semelhantes, pode ser adequado. Ainda não vi qualquer outro caso em que as comparações sejam realmente tão caras :-)

Answer 3

Não parece particularmente familiar, mas os mesclados "inteligentes" são bastante comuns no amplo mundo do software.

Quanto a fazer sentido, isso depende do que você está classificando e do custo relativo das comparações versus alocação de memória. Um tipo que requer até 2*n bytes de memória extra não será uma boa escolha em um ambiente com restrição de memória.

Answer 4

Respondeu agora Wikipedia: Timsort será usado no Java 7, que o copiou do Android.

Answer 5

Timsort também está no Android agora: http://www.kiwidoc.com/java/l/x/android/android/5/p/java.util/c/timsort

Answer 6

A descrição que você vinculou parece completamente geral.