azrael

Andaba yo decidiendo que P=NP cuando me encuentro esto. xDDDD

Si la página no fuera de coña, seguramente haría reír más, por triste que sea.

Atención a lo que dice de Linux. 

Y el que no lo vea, en mi humilde opinión, está ciego o tiene poca visión de futuro.

Por eso son importantes iniciativas como esta.

Que se puede aprender lo mismo divirtiéndose y entendiéndolo lo sabe todo el mundo.

Sin embargo seguimos copiando apuntes como borregos, algo que también todo el mundo sabe que es inútil, las cosas no se memorizan a largo plazo por copiarlas, sino por entenderlas.

Aprendemos muchas cosas estériles.

¿Si todos vemos que se puede mejorar porque no se mejora?

¿Falta de medios? ¿No se ve el camino?

En la escuela ya pensaba que la forma de la que nos enseñaban distaba mucho de ser óptima, tiene que haber algo mejor. Y no hablo de adquirir conocimientos con una pastilla mágica.

¿Porque no se dedican equipos enteros a desarrollar, por ejemplo, software EDUCATIVO para universitarios?

Yo me sé de un par de asignaturas de Ingeniería Informática, que si un software interactivo las explicara decentemente y con un mínimo de diversión y elegancia, podrían venderlo a 100 leuros la unidad, y lo venderían como churros.

P.D.: De más joven probé Adi, una maravilla en aquellos tiempos de 486 y Windows 3.1. La idea era genial, y de verdad que aprendías algo, pero el software distraía demasiado y te permitía juguetear en exceso.

Bueno, estos días escribiré, y sobre todo haré poquito por falta de tiempo.

De momento creo que la mejor forma de hacer el “merge” de dos vectores a y b es la siguiente.

Seleccionamos min(a,b) y situamos el valor máximo de ese vector en el otro mediante búsqueda binaria, ya tenemos fijos los valores superiores, repetimos la operacíon con el minimo, tenemos fijos los inferiores. Repetir la operación hasta tener todos los valores fijos.

Cuando tenga el código de mi versión sencillita del Timsort, lo pondré por aqui, por si a alguien le resulta algúna vez útil o curioso tenerlo en ADA. Porcierto, que no entiendo para que Tim “galopa”.

Revisando Timsort, pese a lo genial y simple de la idea del algoritmo, veo la implementación terriblemente intrincada.

Si la idea es tan potente como pienso, no deberían de hacer falta tantas optimizaciones, con elementos elegidos un poco “al azar” (x ej: a partir de cierto número de elementos usamos selección).

Creo que tiene que haber un algoritmo sencillo y óptimo, posiblemente derivado de la especificación.

Si hay que optimizar algo debería de ser alguna de las ideas, y nunca introducir variables aleatorias con las que sabes que funciona mejor sin saber muy bien porque. Esa es la clase de chapuza que no me gusta en la informática que estoy aprendiendo.

Como mucho, y llevando al limite la técnica, admito que un algoritmo híbrido pueda ser más rápido, por hacerse complicada la evaluación del algoritmo para vectores pequeños.

Otro día explico porque creo que las pilas y los relojes no son más que distracciones.

Al parecer el primer sitio donde aparece un algoritmo similar es un articulo de 1993 que mencionan en el porque Python usa mergesort. Tim lo llama Timsort.

GNU libc también lo usa. Según el autor porque es más eficiente con la jerarquía de caches actual (cuyo mejor caso se asemeja al uso de cintas en los 80).

Aquí lo llaman “adaptive, stable, natural mergesort”. Parece que he llegado 5 años tarde :P.

P.D.: JODER, hasta la idea de usar min(a,b) memoria en la funcion merge es calcada…

Parece que esa versión además cuenta con optimizaciones. El algoritmo simplemente es cojonudo.

P.D.2: Un resumen de la historia. ¿Alguien sabe si Python y Perl lo siguen usando y aún es el algoritmo más rápido de facto?