¿Timsort es de uso general o es específico de Python?
https://stackoverflow.com/questions/154504
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Timsort es una adaptación, estable, mergesort natural. Tiene sobrenatural rendimiento en muchos tipos de parcialmente matrices ordenadas (menos de lg (N!) comparaciones necesarias, y tan pocas como N-1), pero tan rápido como el anterior de Python Híbrido de muestra muy afinado en arreglos aleatorios.
¿Has visto timsort utilizado fuera de CPython? ¿Tiene sentido?
Solución
Sí, tiene bastante sentido usar timsort fuera de CPython, en específico, o Python, en general.
Actualmente hay un esfuerzo en curso para reemplazar el de Java " modificado; ordenar por combinación " con timsort, y los resultados iniciales son bastante positivos.
Otros consejos
El algoritmo es bastante genérico, pero los beneficios son bastante específicos de Python. A diferencia de la mayoría de las rutinas de clasificación, lo que le importa a list.sort (que es lo que usa timsort) de Python es evitar comparaciones innecesarias, porque generalmente las comparaciones son mucho más caras que intercambiar elementos (que siempre es solo un conjunto de copias de puntero) o incluso asignar algo de memoria adicional (porque siempre es solo una matriz de punteros, y la sobrecarga es pequeña en comparación con la sobrecarga promedio en cualquier operación de Python).
Si está bajo restricciones similares, entonces puede ser adecuado. Aún no he visto ningún otro caso en el que las comparaciones sean realmente caras, aunque :-)
No parece particularmente familiar, pero " inteligente " Los mergesorts son bastante comunes en el amplio mundo del software.
En cuanto a si tiene sentido, eso depende de lo que esté clasificando y del costo relativo de las comparaciones frente a la asignación de memoria. Una clasificación que requiere hasta 2 * N bytes de memoria adicional no será una buena opción en un entorno con memoria limitada.
Responda ahora en Wikipedia : timsort se utilizará en Java 7, que lo copió desde Android.
Timsort también está en Android ahora: http://www.kiwidoc.com/java/l/x/android/android/5/p/java.util/c/TimSort
La descripción que vinculó parece completamente general.
