Timsort es un mergesort natural adaptable, estable, . Tiene sobrenatural rendimiento en muchos tipos de parcialmente arreglos ordenados (menos de lg (N!) comparaciones es necesario, y tan pocas como N-1), sin embargo, lo más rápido que el anterior híbrido samplesort altamente sintonizado de Python en matrices aleatorias .¿Es timsort de propósito general o específico de Python?
¿Has visto timsort usado fuera de CPython? ¿Tiene sentido?
Sí, tiene bastante sentido usar timsort fuera de CPython, en específico, o Python, en general.
Actualmente existe un effort underway para reemplazar el "tipo de fusión modificado" de Java con timsort, y los resultados iniciales son bastante positivos.
Java SE 7 usa Timsort como su algoritmo de clasificación ahora. Ver http://www.docjar.com/docs/api/java/util/Collections.html#sort(List) –
La descripción que ha vinculado tiene un aspecto completamente general.
Sí, pero ¿ha visto usar timsort fuera de CPython? – Constantin
No parece particularmente familiar, pero los mergesorts "inteligentes" son bastante comunes en el amplio mundo del software.
En cuanto a si tiene sentido, eso depende de lo que esté ordenando, y el costo relativo de las comparaciones frente a la asignación de memoria. Un tipo que requiere hasta 2 * N bytes de memoria extra no será una buena opción en un entorno con memoria limitada.
El algoritmo es bastante genérico, pero los beneficios son más bien específicos de Python. A diferencia de la mayoría de las rutinas de clasificación, lo que le importa a list.sort de Python (que es lo que usa timsort) es evitar comparaciones innecesarias, porque generalmente las comparaciones son un lote más caras que el intercambio de elementos (que siempre es solo un conjunto de copias de puntero) o incluso asignando algo de memoria extra (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 tiene limitaciones similares, puede ser adecuado. Todavía tengo que ver cualquier otro caso donde las comparaciones son realmente tan caras, aunque :-)
Si las comparaciones son costosas, entonces un algoritmo específico de datos generalmente tendrá un mejor desempeño que uno basado en comparación. –
Esa es una buena observación, y de hecho probablemente sea la razón principal por la que no verás timsort ni nada parecido en la naturaleza. –
Respondido ahora en Wikipedia: timsort se usará en Java 7 que lo copió de Android.
Timsort también está en Android ahora: http://www.kiwidoc.com/java/l/x/android/android/5/p/java.util/c/TimSort
¿por qué haces? sin más contexto, su pregunta no puede ser respondida. – hop
¿Ha notado "¿Ha visto usar timsort fuera de CPython?" ¿parte? – Constantin
lo he notado, y todavía no nos da ningún contexto. ¿Qué aprenderías de un simple "no" como respuesta? – hop