azrael

Este sería el esquema de un algoritmo superadaptativo de ordenación por comparación, a modo de ejemplo. Sería muy rápido para datos presentando cualquier tipo de patrón, seguramente en el peor caso sea n log n, pero está lejos de ser óptimo, ni fácil de implementar. Creo firmemente que para ser óptimo debería de basarse en busqueda binaría en lugar de lineal y que el algoritmo resultante será recursivo y sencillo. Buscar “galopando” (exponencialmente, siguiendo los terminos de la sucesión de Fibonacci) también sería más rápido, pero más lento que una busqueda binaría.  Además pienso que  lo que más importa de un algoritmo es el número de comparaciones, el resto se lo dejo a la implementación.

algoritmo superAdaptativo (v)

ppio

si estaOrdenado(v) entonces

nada;

sinosi estaOrdenadoEnOrdenInverso entonces

invertir(t);

sino

superAdaptativo(maximos);

superAdaptativo(resto);

merge(resto,maximos);

finsi;

fin;

Hay que destacar, que el merge es un merge clasico y lineal, de coste a+b, y que al llamarse con “resto” los datos no serán elementos, sino vectores de elementos consecutivos (para no repetir comparaciones).

Un ejemplo de como debería de funcionar, con números aleatorios.

n=16  log2(16!)=44,25

SuperAdaptativo

4<=6>0<=0<=0<=5<=6>0<=7>0<=7<=8>2<=7<=8>0                                     comps=15

4>[0<=0<=0<=5]>0<=[0<=7]>[2<=7]>0 | 6<=6<=7<=8<=8                           comps=15+5+4=24

[0<=0<=0]<=[0<=0]<=2>0 | 4<=5<=7<=7                                                          comps=24+3+3=30

[0<=0<=0<=0<=0]<=0|2                                                                                         comps=30+1=31

[0<=0<=0<=0<=0<=0]<=2<=[4<=5<=7<=7]>[6<=6<=7<=8<=8]                 comps=31+1+1+1=34

[0<=0<=0<=0<=0<=0<=2<=4<=5]<=[6<=6]<=[7<=7]<=[7<=8<=8]           comps=32+4=36

SuperAdaptativo  Min-Max

4<=6>0<=0<=0<=5<=6>0<=7>0<=7<=8>2<=7<=8>0                                   comps=15

4>0<=0<=0<=2>0|[0<=0<=5]<=7<=7|6<=6<=7<=8<=8                                comps=15+11=26

0<=0|[0<=0]|4>2                                                                                                       comps=26+2=28

[0<=0]<=[0<=0]<=[2<=4]>[0<=0<=5<=7<=7]>[6<=6<=7<=8<=8]              comps=28+1+1+1+1=32

[0<=0<=0<=0]<=[0<=0]<=[2<=4]<=[5<=7<=7]>[6<=6<=7<=8<=8]            comps=32+4=36

[0<=0<=0<=0<=0<=0<=2<=4<=5]<=[6<=6]<=[7<=7]<=[7<=8<=8]             comps=36+3=39

MergesortAdaptativo

4<=6>0<=0<=0<=5<=6>0<=7>0<=7<=8>2<=7<=8>0                                    comps=15

0<=0<=0<=4<=5<=6<=6 | 0<=0<=7<=7<=8 | 0<=2<=7<=8                           comps=15+6+2+3=26

0<=0<=0<=0<=0<=4<=5<=6<=67<=7<=8| 0<=2<=7<=8                               comps=26+11=37

0<=0<=0<=0<=0<=0<=2<=4<=5<=6<=6<=7<=7<=7<=8<=8                        comps=37+15=52

Quicksort

4 6 0 0 0 5 6 0 7 0 7 8 2  7 8 0

4|0 0 0 0 0 2 0 | 6 5 6 7 7 8 7 8                                            comps=15

0 0 0 0 0 2 0 ||4|| 6 5 6 7 7 8 7 8                                          comps=15+6+7=28

||0|| 0 0 0 0 2 0 ||4|| 5 ||6||  6 7 7 8 7 8                             comps=28+5+5=38

||0 0|| 0 0 2 0 ||4 5 6 6 ||7 7 8 7 8                                        comps=38+3+4=45

||0 0 0|| 0 2 0 ||4 5 6 6 7 || 7 8 7 8                                       comps=45+2+3=50

||0 0 0 0|| 2 0 ||4 5 6 6 7 7|| 8 7 8                                        comps=50+1+2=53

0 0 0 0 0 2 4 5 6 6 7 7 7 8 8

Quicksort(no estable)

4 6 0 0 0 5 6 0 7 0 7 8 2  7 8 0

4|0 0 0 0 0 2 0 | 6 5 6 7 7 8 7 8                                             comps=15

0 0 0 0 0 2 0 ||4|| 6 5 6 7 7 8 7 8                                          comps=15+6+7=28

0 0 0 0 0 ||0 2 4|| 5 6 ||6|| 7 7 8 7 8                                    comps=28+4+1+4=37

0 0 0 0 ||0 0 2 4 5 6 6|| 7 7 ||7||8 8                                     comps=37+1+1=39

0 0 0 ||0 0 0 2 4 5 6 6 7 7  7 8 8||                                         comps=39+2=41

0 0 ||0 0 0 0 2 4 5 6 6 7 7  7 8 8||                                         comps=41+1=42

0 0 0 0 0 2 4 5 6 6 7 7 7 8 8

Las barras “|” separan “máximos” de “resto”, y los corchetes [] vectores ya comparados.
La zona entre dos barras “||” está ordenada.

El peor caso de un algoritmo superadaptativo, será cuando nos encontremos la ordenación mínima en el vector de n datos, y en los sucesores vectores que analice el algoritmo, es decir, estos dos casos:

A<=B>C<=D>E<=F                   o                   A>B<=C>D<=E>F

A<=C>E y B<=D>F                    o                  A>C<=E y B>D<=F

A<=E y B<=F                              o                   A>E y B>F

A<=E<=C<= B<=F<=D             o                  D<=F<=B<=C<=E<=A

Si esto es de verdad así, yo lo llamaría acordeón :P.

Bueno, como ya sabemos que P=NP (:P).

La idea que proponía hace un tiempo era hacer una base de datos enorme y compartida, de todos los mejores algoritmos para realizar cualquier función. Usaríamos un lenguaje funcional tan simple como el hablado para resolver cualquier problema.

Aprovechando que P=NP, probablemente siempre sepamos el mejor algoritmos para resolver un problema.

De modo que en esa enorme base de datos ya no necesitaremos tener código. Asúmiendo que se deriven los algoritmos óptimos de sus especificaciones, con guardar especificaciones ligadas al nombre de los algoritmos y/a/o sus sinónimos, basta.

¿Fácil, sencillo y para toda la familia, no?

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.