azrael

A la hora de añadir un elemento a un vector ordenado, es evidente que el coste óptimo es log(n) -mediante busqueda binaria-.

El error que se comete es creer que hacer esto mismo con varios elementos nos lleva necesariamente a algo proporcional.

Para añadir n elementos a un vector ordenado (o lo que es lo mismo, ordenar n elementos), parece que el coste vaya a ser n log n en el peor caso. Sin embargo esto tan sólo es cierto si no tenemos en cuenta las realciones entre los elementos. Por lo tanto n log n sólo es cota para el peor caso de un algoritmo de ordenación óptimo.

Para ilustrar esto comparemos la búsqueda binaria con los algoritmos anteriores.

BusquedaBinaria(estable)

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

4<=6 comps=1

0<=4<=6 comps=2

0<=0<=4<=6 comps=4

0<=0<=0<=4<=6 comps=6

0<=0<=0<=4<=5<=6 comps=9

0<=0<=0<=4<=5<=6<=6 comps=12

0<=0<=0<=0<=4<=5<=6<=6 comps=15

0<=0<=0<=0<=4<=5<=6<=6<=7 comps=19

0<=0<=0<=0<=0<=4<=5<=6<=6<=7 comps=23

0<=0<=0<=0<=0<=4<=5<=6<=6<=7<=7 comps=27

0<=0<=0<=0<=0<=4<=5<=6<=6<=7<=7<=8 comps=31

0<=0<=0<=0<=0<=2<=4<=5<=6<=6<=7<=7<=8 comps=35

0<=0<=0<=0<=0<=2<=4<=5<=6<=6<=7<=7<=7<=8 comps=39

0<=0<=0<=0<=0<=2<=4<=5<=6<=6<=7<=7<=7<=8<=8 comps=43

0<=0<=0<=0<=0<=2<=4<=5<=6<=6<=7<=7<=7<=8<=8 comps=47

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.

La cota log(n!) (O (n log(n))), es la cota inferior (y superior) de un algoritmo de ordenación por comparación óptimo no adaptativo.

Sin embargo es la cota superior de un algoritmo de ordenación por comparación óptimo adaptativo.

La cota inferior de un algoritmo adaptativo es O(n).

Por lo tanto el coste de un algoritmo adaptativo óptimo se situará entre O(n) y O(n log n).

Para comprobar si mis hipótesis  son correctas, estoy trabajando en un algoritmo recursivamente adaptativo. Puede que no sea practico, entre otras cosas por no tener muy en cuenta el modelo de cachés, pero seguro que será interesante (según creo el coste medio estará rozando el n log n, pero por debajo ;).

Si en Quicksort se usara la comparacion “<=”, para los datos de antes de la posicion de pivote, y “<” para los datos de despues del pivote, el algoritmos sería estable, y posiblemente mejoraría su rendimiento en situaciones de repetición de claves.

EDIT: La respuesta dos post más adelante “Ejemplo superadaptativo”, el quicksort estable pierde rendimiento.

Hoy me pasaba algo rarísimo, en una practica de algoritmos de ordenación, al utilizar quicksort en su caso medio el coste era

n log n, en el peor (para un vector ordenado) cuadrático, pero con vectores MUY grandes, ambos costes convergían.

Garantizo que nada en el código estaba mal, y ha sido un profesor quien ha dado con el quid de la cuestión. Podría dejar la resolucióndel enigma al lector… pero no sé si hay datos suficientes para deducir que pasaba.

Estaba usando muy pocas claves distintas (27 para vectores de 100000 elementos). ¿Porque hacía eso que el caso peor y el medio tuviran un coste similar?

La explicación es sencilla; el Quicksort tradicional tiene 3 casos malos (orden cuadrático):

-un vector ordenado

-un vector inversamente ordenado

-un vector de elementos iguales (la comparacíon “<=” lo hace equivalente a un vector ordenado).

Teniendo pocas claves en un vector muy grande, se forman grandes grupos de claves idénticas.

Solución: Usar muchas claves diferentes (todo el rango de enteros en ADA).

Este es otro argumento a favor de los algoritmos de ordenación adaptativos, normalmente usar pocas claves será una gran ventaja. ¿Pero y con un texto?Muchas letras iguales seguidas no habrá… pero con 27 claves (la letras), seguro que hay grandes grupos ordenados en la mayor parte de los vectores. Además, un texto no es aleatorio.

Esta, me parece una explicación sencilla, bonita y para toda la familia.

Pero atención, porque le faltan bastantes optimizaciones.

En este documento, explican como mediante una desordenación aleatoria de los elementos del vector a ordenar, los algoritmos adaptativos de ordenación son más rápidos.

Es un punto de vista probabilistico, y supongo que presupone que el vector a ordenar no está inicialmente desordenado de forma realmente aleatoría.

De todas formas, un mergesort adaptativo no es la panacea. Su gran virtud es poder usarlo en cualquier caso con una gran eficacia. Por ejemplo si alguien “se equivoca” y decide ordenar un vector ya ordenado, o un vector que contiene ya un vector ordenado. Quicksort es mucho más facíl de implementar, pero más lento (y no sólo en estos casos).

P.D.: El algoritmo en el que aplican esta mejora no es “Timsort”, sino uno de sus predecesores.

P.D.2:Algún día acabaré mi versión de Timsort… más tarde haré algo mejor :p.

Para todo el que le interesen los problemas de optimización, y en especial el TSP, desde su entrada en la Wikipedia, he llegado a unos documentos interesantes.

Me llama la atención especialmente que para aproximaciones igual de buenas a las personas les cuesta menos calcularlas que usando algoritmos sofisticados.

Le acabo de dar algunas vueltas, y estoy casi seguro de que se puede hacer un merge con espacio adicional constante . Sean A y B los dos vectores a mezclar, la complejidad computaciotnal de dicho algoritmo sería siempre inferior a AxB.

El único problema que veo es que en el procesador iba a usar registros que te cagas, y que sería realmente complejo de programar, la búsqueda binaría incluiría a menudo elementos que no están en su posición original en el vector.