Timsort es un algoritmo de ordenación eficiente para datos del mundo real y no creado en un laboratorio académico. Tim Peters creó Timsort para el lenguaje de programación Python en 2001. Timsort primero analiza la lista que está tratando de ordenar y luego elige un enfoque basado en el análisis de la lista. Desde que se inventó el algoritmo se ha utilizado de forma predeterminada en Python, Java y en GNU Octave. Su complejidad es O (n log n).
|
etiquetas: timsort , algoritmo de ordenación , python , java , tim peters
Kernel panic
He verificado con mi jdk (12). Por internet he mirado el git de openjdk y sigue asi.
...que además es un excelente método de justificar nuevos procesadores mas rápidos, multinucleo, multihilo, con refrigeración líquida, y varios carros de RAM overclockeada con RGB a juego con la caja ^^.
È voilá! Ya podremos tener la lista de la compra del mercado ordenada por estanterias
Por ejemplo para arrays pequenyos usa insertion o counting sort, para arrays grandes quicksort o mergesort (esta vez dependiendo de cuan desordenados esten en vez del tamanyo).
Lo chulo es que una vez empieza quicksort, en las sucesivas llamadas recursivas de ordenacion cambia a counting sort para ordenar las particiones si considera que va a ser mas eficiente.
Ahora en serio, Timsort se utiliza al ordenador arrays de objetos, pero no se usa para ordenar primitivas
EDIT: Y just ahora veo que has comentado que se usan distintos algorimos en #5
En cualquier caso:
JDK8u: hg.openjdk.java.net/jdk8u/jdk8u/jdk/file/69c4f673b33e/src/share/classe
JDK (tip): hg.openjdk.java.net/jdk/jdk/file/e84d8379815b/src/java.base/share/clas
Me gustaria saber cual es el mejor algoritmo de ordenacion capaz de utilizar el maximo de procesadores donde se este ejecutando y sacarle provecho.
Según eso gana el Radix Sort, no?
es.wikipedia.org/wiki/Algoritmo_de_Grover
Respecto a la noticia, trimsort no es un algoritmo per se, sino un selector de algoritmos. En cada ocasion, trimsort estima que algoritmo formal utilizar.
La realidad es que no hay un algoritmo mas rapido, sino un algoritmo más apto para cada una de las tareas. no es lo mismo ordenar un set aleatorio que uno semiordenado, que uno totalmente revertido, o mas o menos ordenado. en cada caso, hay un algoritmo mejor, pero ninguno será bubble sort.
Me quedo con que con los mismos recursos, y en pocas líneas de código se puede ser más genio que otros.
Juraría que los desarrolladores, además del algoritmo de burbuja, han inventado nuevos métodos súper avanzados para convertir en mierda el software.
Y no es broma, he visto de desarrolladores de empresas de juegos, incluidos los triple A (que se supone que en juegos prima la eficiencia) decir e implementar cosas absolutamente increíbles, que no creerias.
¿Cuál es la diferencia entre el mundo real y el mundo académico?
Si diseño la teoría de un algoritmo y pruebo su velocidad con teoría (el big O)..¿no servirá en el mundo real? ¿en serio?
Acordémonos del famoso efecto 2000. Todo porque se usaban 2 dígitos para el año. Daba idea de las restricciones de memoria o capacidad con las que se trabajaba. Recuerdo las épocas en las que usabas usabas una variable de 1-2 bytes en vez de una de 4 porque así ganabas en memoria y velocidad de proceso. Hoy en día coges una grandota y así te evitas complicaciones futuras.
Recuerdo en el último curso que hice que ante una pregunta sobre la eficacia de un entity framework vs otras alternativas su respuesta básicamente era que la memoria RAM es barata y que te sale más a cuenta montar tu base de datos en memoria (con el evidente soporte paralelo para que la vaya haciendo respaldo en un medio no volátil) que no plantearse alternativas.
Pero bueno, seguro que alguien se fue a la cama contento pensando "malditos académicos que no hacen nada que funcione".
Por otra parte, las optimizaciones que se hacen hoy día en tiempo de compilación y ejecución son una barbaridad, por lo que muchas veces ir de listo es improductivo por triplicado: optimizas lo que iba a optimizar el intérprete/compilador/jit, dejas un código peor y más difícil de seguir, el compilador no puede hacer todas las optimizaciones o lo cuesta más.
Estoy de acuerdo en que esto no nos debe llevar a malacostumbrarnos, pero el tiempo de hacer microoptimizaciones pasó hace bastante, hoy en día prima el código desacoplado y de fácil mantenimiento.
Eso sí, el conocimiento de algoritmia y complejidad computacional es obviamente necesario y puede evitar sobredimensionado de infraestructura en muchas ocasiones, pero eso dista mucho de no utilizar más RAM cuando es sumamente barata y consume muy poco.
En resumen: todo es cuestión de trade offs
Quicksort es un algoritmo de ordenación fabuloso que puede implementarse en cualquier lenguaje, incluso en los no eficientes y para vagos y torpes como Java.
Otro ejemplo es cuando hablo de Unit of Work y otros patrones, haciendo referencia al caso que expone otro usuario (a los demás os cité porque estabais en el hilo).
Si te lo has tomado a pecho y como algo personal... Por algo será
Llevas poco dice, me meo.
Que te da asco de java? En que no es eficiente java? Por que es para torpes?
Que un lenguaje se pueda usar de forma "vaga" es positivo. Para que vas a tener que reimplementar la rueda si ya esta hecha? Acaso crees que vas a programar librerias o estructuras de datos de uso comun mejor que los desarrolladores del lenguaje?
Si quieres usar un HashMap, ya lo tienes implementado. No vas a meter la pata con la funcion de hash por que el propio lenguaje tiene un metodo para ello Objects.hash(atributos...). Si necesitas algo particular puedes implementarlo. Si implementas una tabla hash a mano por gusto (sin necesitarlo), es que eres retrasado y mereces que te despidan
Por otro lado, el del artículo hace un análisis estadístico para predecir el algoritmo que podría tardar menos (que sólo mejoría en un factor fijo, con lo que la complejidad sería la misma). Además en casos en los que el array sea inferior a cierto tamaño, el propio análisis será más lento que utilizar un método de ordenación concreto directamente.
Otros factores que influyen a la hora de elegir un algoritmo para un uso concreto también es la memoria que necesita o la posibilidad de ejecutar en paralelo.