Timsort est-il à usage général ou spécifique à Python?

Question

Timsort est un mergesort adaptatif, stable et naturel. Il a des performances surnaturelles sur de nombreux types de tableaux partiellement ordonnés (moins de lg (N!) Comparaisons nécessaires, et aussi peu que N-1), mais aussi rapide que le précédent hybride d'échantillons hautement réglé de Python sur des tableaux aléatoires.

Avez-vous vu timsort utilisé en dehors de CPython? Est-ce que ça fait du sens?

Answer 1

Oui, il est assez logique d'utiliser timsort en dehors de CPython, en particulier, ou Python, en général.

Il y a actuellement un effort en cours pour remplacer le «tri par fusion modifié» de Java par timsort, et les premiers résultats sont plutôt positifs.

Answer 2

L'algorithme est assez générique, mais les avantages sont plutôt Python spécifiques. Contrairement à la plupart des routines de tri, ce Python de la liste.de tri (ce qui est utilise timsort) se soucie est pour éviter les comparaisons, parce que généralement, les comparaisons sont beaucoup plus cher que la permutation des éléments (ce qui est toujours juste un ensemble de pointeur de copies) ou même à consacrer plus de mémoire (parce que c'est toujours un tableau de pointeurs, et la charge est faible par rapport à la moyenne des frais généraux dans toute Python opération.)

Si vous êtes avec des contraintes similaires, alors il peut être approprié. Je n'ai pas encore vu tous les autres cas où les comparaisons sont vraiment très cher, cependant :-)

Answer 3

Cela ne semble pas particulièrement familier, mais les fusionnements «intelligents» sont assez courants dans le vaste monde des logiciels.

Quant à savoir si cela a du sens, cela dépend de ce que vous triez et du coût relatif des comparaisons par rapport à l'allocation de mémoire. Un tri qui nécessite jusqu'à 2 * N octets de mémoire supplémentaire ne sera pas un bon choix dans un environnement limité en mémoire.

Answer 4

Réponse maintenant sur Wikipedia : timsort sera utilisé dans Java 7 qui l'a copié depuis Android.

Answer 5

Timsort est également dans Android maintenant: http://www.kiwidoc.com/java/l/x/android/android/5/p/java.util/c/TimSort