Timsort est-il polyvalent ou spécifique à Python?
https://stackoverflow.com/questions/154504
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Timsort est une solution adaptative, stable, mergesort naturel. Il a surnaturel performance sur de nombreux types de partiellement rangées ordonnées (moins que lg (N!) les comparaisons nécessaires, et aussi peu que N-1), pourtant aussi rapide que le précédent de Python samplesort hautement hybride sur tableaux aléatoires.
Avez-vous utilisé timsort utilisé en dehors de CPython? Cela a-t-il un sens?
La solution
Oui, il est assez logique d'utiliser timsort en dehors de CPython, en particulier, ou de Python, en général.
Un effort en cours est en cours pour remplacer celui de Java. fusionner le tri " avec timsort, et les premiers résultats sont assez positifs.
Autres conseils
L'algorithme est assez générique, mais les avantages sont plutôt spécifiques à Python. Contrairement à la plupart des routines de tri, le paramètre list.sort de Python (ce qui utilise timsort) a pour objectif d'éviter les comparaisons inutiles, car les comparaisons coûtent généralement beaucoup plutôt que d'échanger des éléments pointeur) ou même allouer de la mémoire supplémentaire (car il s’agit toujours d’un tableau de pointeurs, et la surcharge est réduite par rapport à la moyenne des opérations Python.)
Si vous êtes soumis à des contraintes similaires, cela peut convenir. Je n'ai encore vu aucun autre cas où les comparaisons sont vraiment si chères, cependant: -)
Cela ne semble pas très familier, mais "intelligent". Les fusions sont assez courantes dans le vaste monde du logiciel.
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 type qui nécessite jusqu'à 2 * N octets de mémoire supplémentaire ne sera pas un bon choix dans un environnement soumis à des contraintes de mémoire.
Réponse maintenant sur Wikipedia : timsort sera utilisé dans Java 7 qui l'a copié à partir d'Android.
Timsort est également disponible sur Android: http://www.kiwidoc.com/java/l/x/android/android/5/p/java.util/c/TimSort
La description que vous avez associée est complètement générale.
