Portada
mis comunidades
otras secciones
![Timsort, el algoritmo de ordenación más rápido del que nunca has oído hablar [ENG]](https://cdn.mnmstatic.net/cache/30/be/media_thumb_2x-link-3194429.jpeg?1570633146)
#5:
#3 He revisado el codigo por curiosidad y en la clase Arrays se utilizan diferentes metodos dependiendo de la estructura del array a ordenar.
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.
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.
#8:
#3 No, completamente erronea. Habia oido hablar de Timsort antes
Ahora en serio, Timsort se utiliza al ordenador arrays de objetos, pero no se usa para ordenar primitivas
En cualquier caso:
JDK8u: http://hg.openjdk.java.net/jdk8u/jdk8u/jdk/file/69c4f673b33e/src/share/classes/java/util/Arrays.java#l1431
JDK (tip): http://hg.openjdk.java.net/jdk/jdk/file/e84d8379815b/src/java.base/share/classes/java/util/Arrays.java#l1435
Ahora en serio, Timsort se utiliza al ordenador arrays de objetos, pero no se usa para ordenar primitivas
editado:
Y just ahora veo que has comentado que se usan distintos algorimos en #5En cualquier caso:
JDK8u: http://hg.openjdk.java.net/jdk8u/jdk8u/jdk/file/69c4f673b33e/src/share/classes/java/util/Arrays.java#l1431
JDK (tip): http://hg.openjdk.java.net/jdk/jdk/file/e84d8379815b/src/java.base/share/classes/java/util/Arrays.java#l1435
#3:
Medio erronea; en java quicksort sigue siendo el metodo de ordenacion. Se puede ver en el codigo fuente de java.util.Arrays.
He verificado con mi jdk (12). Por internet he mirado el git de openjdk y sigue asi.
He verificado con mi jdk (12). Por internet he mirado el git de openjdk y sigue asi.
#17:
Para los que no entiendan del tema o les suene a chino, estos GIFs dan una idea visual de cómo funcionan los distintos algoritmos de ordenación: https://m.imgur.com/gallery/GD5gi
Comentarios
Timsort, ordéname el armario...
Kernel panic
Medio erronea; en java quicksort sigue siendo el metodo de ordenacion. Se puede ver en el codigo fuente de java.util.Arrays.
He verificado con mi jdk (12). Por internet he mirado el git de openjdk y sigue asi.
#3 He revisado el codigo por curiosidad y en la clase Arrays se utilizan diferentes metodos dependiendo de la estructura del array a ordenar.
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.
#3 No, completamente erronea. Habia oido hablar de Timsort antes
Ahora en serio, Timsort se utiliza al ordenador arrays de objetos, pero no se usa para ordenar primitivas
En cualquier caso:
JDK8u: http://hg.openjdk.java.net/jdk8u/jdk8u/jdk/file/69c4f673b33e/src/share/classes/java/util/Arrays.java#l1431
JDK (tip): http://hg.openjdk.java.net/jdk/jdk/file/e84d8379815b/src/java.base/share/classes/java/util/Arrays.java#l1435
#26 Corrección, no es #6 sino #8
Sabía lo que dijo #3, pero no sabía lo que dijo #5 o #6
#3 lo de java (lenguaje que me da asco) no tiene nada que ver con quicksort.
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.
#31 Que me estas contando? Leete el codigo fuente anda.
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
Para los que no entiendan del tema o les suene a chino, estos GIFs dan una idea visual de cómo funcionan los distintos algoritmos de ordenación: https://m.imgur.com/gallery/GD5gi
Muy interesante, gracias #0
#18 Prima mas sacar las cosas a tiempo. Y asi salen como salen.
#19 #18 #14 #22 es que la RAM es barata y el software resultante es más mantenible si se usa un ORM (deduzco que eso es EF, no he trabajado con él). Otra cosa es que no conozcas los patrones detrás del Framework de turno (ORM en este caso, que usará Active Récord, Data Mapper, Unit of Work...) y no lo uses bien, con lo que en lugar de las ventajas consigues las desventajas y otras que te creas por el camino.
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
#25 Si no entiendes la diferencia entre optimizaciones de código y usar algoritmos eficientes mejor dedícate a otra cosa, se te nota que llevas poco tiempo y has querido dártelas de listo
#28 si supieses leer te darías cuenta de que lo comprendo perfectamente y que respondía a varios comentarios a la vez (donde se mezclaban ambas cosas). Y este caso del meneo es un ejemplo de optimización en tiempo de ejecución, y dónde precisamente el ir de listo y tratar de optimizar utilizando un algoritmo concreto no agiliza sí no lo opuesto.
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á . Cry me a River.
Llevas poco dice, me meo.
Y donde ha quedado el bueno y fiel burbuja???
...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
#4 "Y donde ha quedado el bueno y fiel burbuja???"
Está trabajando. Viene en un momento.
#4 y seguir contribuyendo al cambio climatico con software ineficiente
#14 Me han quitado la infancia, ¿cómo se atreven?
#4 Viendo la basura lenta de software moderno que se hace, sólo hay que cargar cualquier programa que imagines, incluidos los súper simples, en un ordenador un poco antiguo o con disco duro mecánico y ver que tarda una eternidad en cargarse y ejecutarse:
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.
#18 es la ley del mínimo esfuerzo, cuanto más potente y/o barato se va haciendo el hardware más gandul se vuelve el desarrollador, porque total, si el programa va demasiado lento o necesita más memoria resulta más fácil, cómodo y barato comprar más memoria o poner un procesador más potente que refactorizar el programa, optimizarlo o lo que haga falta.
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.
#18 los triple a tampoco se salvan. Utilizan la magia de abstracciones en forma de frameworks, motores gráficos, sdks de desarrollo... a costa de sacrificar un poco la eficiencia para reducir el tiempo de desarrollo brutalmente. El hardware actual es muchísimo más potente de lo que parece.
#4 el de la baraja... ese lo inventaron en el oeste fijo
Según eso gana el Radix Sort, no?
#10 depende, en complejidad sí es mejor, pero solo sirve para ordenar numeros o cadenas (no es un algoritmo de comparación que permite ordenar elementos de cualquier tipo siempre que tengan la operación menor-qué definida) y tampoco es in-place de manera que requiere alojar memoria intermedia y copiar los elementos o referencias a estos, lo cual en la práctica lo hace más lento en la mayoría de casos.
La frase "es un algoritmo de ordenación eficiente para datos del mundo real y no creado en un laboratorio académico." destila bastante desprecio y prejuicios hacia el mundo académico.
¿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?
#21 Venía a decir esto. Aparte de que el algoritmo se basa en combinar otros algoritmos que sí fueron creados en el mundo académico. Por no hablar del concepto mismo de algoritmo, lenguaje de programación, ordenador...
Pero bueno, seguro que alguien se fue a la cama contento pensando "malditos académicos que no hacen nada que funcione".
#21 seguramente se diferencian en que te clavarán una pasta en licencias por usarlo, y por supuesto con tus datos sera más lento que cualquier otro algoritmo
Timsort Vs Marie Kondo FIGHT!!!
Muy interesante este algoritmo de ordenacion, pero al final solo usa un procesador.
Me gustaria saber cual es el mejor algoritmo de ordenacion capaz de utilizar el maximo de procesadores donde se este ejecutando y sacarle provecho.
#9 En un futuro próximo, el algoritmo de Grover, O(N1/2):
https://es.wikipedia.org/wiki/Algoritmo_de_Grover
#9 si paralelizas el proceso, podria ser mergesort, bastaria con ejecutar cada iteracion en un procesador distinto.
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.
#9
¿Mergesort tal vez?
#9 el merge Sort por ejemplo es paralelizable
el ejemplo que facilita en python no funciona
Muy interesante. Pero se me queda grande para mi capacidad y tiempo que dispongo. Pa que mentir.
Me quedo con que con los mismos recursos, y en pocas líneas de código se puede ser más genio que otros.
Yo también diría que es medio errónea: la "rapidez" que debería decir orden de compeljidad de Timsort es la misma que Quicksort: O ( n log n)
#20 O ( n log n) significa que se comportan de esa manera (no sobrepasan n log n), pero no todos son iguales uno puede ser consistentemente más rápido que los otros (en la mayoría de los casos) o más rápido en casos particulares (como por ejemplo, si los elementos están más o menos ordenados, o están ordenados al revés de como se quiere, etc)
#20 totalmente, la mejor complejidad en tiempo para un algoritmo de ordenación es O(n • log n) que es la que ya tienen bastantes algoritmos.
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.