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, 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.

Hay una idea que lleva rondándome ya mucho tiempo.

Para empezar tenemos el hecho, de que programar, sin errores, hoy por hoy, parece imposible.

Por otro lado es una técnica difícil de dominar.

Ahora expongo mi idea, que puede que sea imposible de llevar a la práctica por su complejidad, pero haría de la programación un juego de niños.

Ya conté algo de que lo ideal sería un diálogo en el que tu le indicases, abstractamente, al ordenador, que es lo que deseas hacer.

La primera parte de la idea es buscar un lenguaje de programación que no pueda fallar, y ahí esta SPARKAda.

La segunda es montar sobre ese lenguaje otro mucho mas complejo. Esto llevará posiblemente a una sobrecarga algorítmica bastante importante, pero no se puede hacer una tortilla sin romper los huevos ;).

Con este segundo lenguaje (lo llamare miSOl, si de verdad lo hago algún rato), la idea sería muy sencilla, hay que hacer una base de datos enorme, de algoritmos (una librería, del tamaño de la de Alejandría).

En esta base de datos habrá un algoritmo para cada propósito, pero no se trata de hacer un sistema experto con una librería enorme de per se, la idea es infinitamente más simple y cómoda.

Resumiendo, tu lo que haces es pedir hacer un programa, eliges que tipo de programa quieres hacer y su nombre, luego, siguiendo un procedimiento de diseño descendente, explicas de forma general lo que hace el programa.

En cada parte de lo que has dicho que hace explicas lo que hace esa parte, y así sucesivamente, hasta que reduces el problema a  uno que se pueda escribir en un par de lineas de SPARK. Este programita en SPARK se añade a una gigantesca base de datos, y cada vez que quieras volver a hacer eso, directamente usará ese algoritmo.

Aún tengo que pensar que estructura habria qe usar para esa base de datos, y creo que aún no se me han ocurrido ni una facción de los problemas que puedan aparecer(el principal creo que sería automatizar la especificación en SPARK, pero de verdad pienso que la idea es realizable, y que puede simplificar la programación  e incrementar su velocidad y fiabilidad de forma exponencial (al fin y al cabo es nuestro lenguaje el que dominamos, incluso pensamos con él).