azrael

He modificado la imagen que en wikipedia ilustra Mergesort (de dominio público) para mostrar como funciona mi Optimal Comparison Sort.Recuerdo que para mezclar tres vectores, se usa el Merge3.Aprovecho para comentar que es el equivalente a un árbol balanceado.Las comparaciones en este caso son 10 para mi Optimal Comparison Sort , 14 para Mergesort y 15 para Quicksort eligiendo como pivote el elemento central. Espero un comportamiento proporcional para vectores aleatorios más grandes. (more…)

Sabemos la forma óptima de mezclar tres vectores ordenados, la de mezclar cuatro no será tan sencilla. (more…)

De momento (creo que) tenemos el algoritmo de merge óptimo para dos vectores… pero nuestro objetivo va más allá.La idea es hallar un merge para N vectores, pero como no parece fácil, vayamos pasito a pasito.Lo hemos hecho para dos, intentémoslo para tres vectores. Sean tres vectores, v1, v2 y v3, parece que una generalización del algoritmo anterior debería de empezar por comparar los centros, al menos uno de ellos.Como queremos que el merge sea estable, las posiciones de los vectores si que importan, por lo tanto empezaremos por el vector central.

 v1: |1|2|3|4|5|6|7|8|9|  

v2: |1|2|3|4|5|6|7|8|9| 

v3: |1|2|3|4|5|6|7|8|9|  

Seguimos  comparando centros de vectores, por lo tanto elegiremos el central de los centros como pivote, y empezaremos por comapararlo con los otros dos centros.

Tenemos 5<=5<=5.

Por lo tanto: 

v1: |6|7|8|9|   

v2: |1|2|3|4|5|6|7|8|9|

v3: |1|2|3|4| 

Ahora tenemos 7>5>2, por tanto:

v1:   |6|   

v2: |1|2|3|4|5|6|7|8|9|v3: |3|4|

 6>5>3

v1:  v2: |1|2|3|4|5|6|7|8|9|v3: |4|   

5>4

En resumen, hemos separado los tres vectores en relación a nuestro pivote que era el elemento más central, por ser del que más información se obtiene al compararlo.

Tenemos

|1|2|3|4|5|         |6|7|8|9|

|1|2|3|4|     5     |6|7|8|9|

|1|2|3|4|             |5|6|7|8|9|

Tán sólo nos queda repetir la operación de forma recursiva, y tenemos el mejor merge que haya visto un mergesort, usandolo en lugar del merge tradicional, se reduciría el número de comparaciones y sobre todo el movimiento de datos, al mezclar los vectores de forma óptima de tres en tres.

  (more…)

Ayer, leyendo el blog del autor del port para PSP del emulador de N64 Daedalus, ley una referencía a un documento sobre Dynamo.

Parece ser que Dynamo era (y espero que siga siendo) el nombre de un proyecto de software genial.

Básicamente se trata de una capa de software “invisible”, que mediante recompilación dinamica (DynaRec), es capaz de aumentar el rendimiento de código nativo en una maquina. De esta forma el rendimiento conseguido es basntante mayor que el overhead de la propia DynaRec.

Que este proyecto funcionase, demuestra la viabilidad de una de mis locas ideas. La tuve hace ya años, y básicamente consiste en crear un virus que aproveche los ciclos libres de la CPU para optimizar el código en ensamblador de los programas que haya por ahí rondando en nuestra computadora.

Podría ser útil, ¿verdad?

Es increíble lo que dan de sí los algoritmos.

De hecho sirven para TODO, una verdadera pasada.

El enlace va directo a un video que muestra los resultados de aplicar un algoritmo de escalado de imagenes en función de su contenido.

El algoritmo identifica zonas de la imagen en función de la importancia (supongo que de la cantidad de información que aporta; por ejemplo muchos cambios de color serán mucha información, una zona calida, un suave degradado será poca información, una zona fría), y trata de conservar las zonas más importantes en detrimento de las menos.

P.D.: La fuente son los foros de macuarium .