azrael

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?

“modified merge sort with exponential search intended for sorting data with pre-existing order” En la librería estándar de C de algún openBSD. Al menos parece que se comporta parecido.

Por otro lado, en un PDF del año de la pera (97), una versión de mergesort con 4 punteros gana a quicksort iterativo en el caso medio.

El algoritmo (que de momento seguiré llamando miMerge, hasta que descubra si tiene otro nombre), tiene bastante en común con el Bitonic Mergesort, aunque este no ordena de forma tan “inteligente”. El Bitonic Mergesort, por otro lado tiene la ventaja de requerir un hardware más simple, y por lo tanto se usa para aprovechar su gran paralelización en GPU’s.

¿Y cual era el problema de miMerge? Al parecer efectivamente es asimptoticamente óptimo en el caso medio. También es optimo para vectores ya ordenados, pero heredá el gran fallo del merge sort original: utiliza o(n) memoría.

El bitonic mergesort sin embargo no tiene ese problema, pero a costa de pasar a un tiempo medio n log^2 n, que no es óptimo, y también será este su coste en el caso de vectores ordenados.

Así pues, parece que el gran problema de este algoritmo sigue estando en encontrar una función merge óptima, que sea in place. Puede que eso sea demasiado para mi… ya veremos.

Las dos operaciones extra que me salen deben de ser las inversiones, pero me extraña, porque estaba convencido de que en el peor caso miMerge haría exactamente las mismas operaciones que mergesort. Creo que no tienen porque hacerse inversiones, si no sólo tener en cuenta que ese trozo de vector esta ordenado en orden inverso.

Este algoritmo iterativo está inspirado en Merge Sort de Von Neuman.

La idea básica es que Merge Sort no aprovecha el orden intrínseco de cualquier vector desordenado (como mínimo los elementos estarán ordenados de dos en dos).

Los objetivos (que no sé si he alcanzado, porque son ideales), són:

-Un algoritmo que aproveche al máximo el orden existente en un vector dado.

-Ordenación en N para un vector ya ordenado, ordenación en 2N para un vector ordenado en orden inverso.

-Ordenación en n log n para el peor caso.

-Numero de comparaciones mínimo, exactamente igual al de mergesort.

Como se ve, estos dos últimos son los más difíciles (de hecho supongo que el número de comparaciones de mergesort no es mínimo).

Como aún no he visto ningún algoritmo de este estilo propongo el mío.

Se buscan los (i-a+1) primeros elementos ordenados (en orden creciente o inverso), luego los siguientes (i-a+1) elementos ordenados y se mezclan los dos vectores ordenados para formar un vector resultado, ordenado en orden creciente, se continua de la misma forma, mezclando los siguientes (i-a+1) elementos ordenados con el vector resultado precedente.

a será por lo tanto el indice del primer elemento de un trozo de vector ordenado, e i el indice del último elemento de ese mismo trozo de vector ordenado

algoritmo miMerge (v: ES vector) es

orden:bool;

a,i:tpIndice;

ppio

i:=1;

a:=i;

orden:=directo;

mQ no i>=DIM(v)

si v[i]<v[i+1]

si orden = directo

sigue;

si_no –orden =inverso

mergeInvirtiendo(a,i);

orden:=directo;

a:=i+1;

fSi;

si_no — v[i]>=v[i+1]

si orden = directo

merge(a,i);

orden:=inverso;

a:=i+1;

si_no –orden =inverso

sigue;

fSi;

fSi;

i:=i+1;

fMQ;

fin;

P.D.: Sí el algoritmo está mal, o su coste en el peor caso es N!, que nadie me tiré una piedra a la cabeza, con explicarme lo que está mal e intentar optimizarlo valdría.

P.D.2:Después del Paso De Ecuador escribo mergeInvirtiendo y merge :P. Adelanto que mergeInvirtiendo, invierte y luego mezcla.