azrael

Hoy es el día en el que empieza el periodo de desarrollo para el Segundo Concurso Universitario de Software Libre (II CUSL) en el que me he inscrito.Intentare implementar un algoritmo de ordenación por comparación óptimo en el número de comparaciones en ADA (deseadme suerte, que me hará falta .A ver como va esto de los feeds RSS para poder enviarselos ;). 

Lo que decía sobre la cota de los algoritmos de ordenación, explicado aquí con una bonita demostración.

Proof of the lower bound for the asymptotic running time of comparison sort algorithms

The worst case running time of any comparison sort algorithm is Ω(nlgn)

Let T be the decision tree for all possible comparisons between elements of a list . So T is complete and the label of each vertex v of the tree are of the form x_i:x_j and v is source of two edges labeled and < . The comparisons made by a sorting algorithm running over X corresponds to a path from the root of T to a leaf. One should note that for each possible permutation P of the elements in X there is such a path. So T has at least n! leaves. We know that T is a binary tree, so it has a maximum of 2^h leaves, where h is it’s height. We have and

.

Summarizing, h = Ω(nlgn)

Cada vez que pienso en ordenación y se me ocurre algo pienso que como lo hacía tan complicado, y que cómo lo complican tanto si es “tan fácil”.

Ordenar un vector de n elementos con k vectores ordenados en su interior, de forma óptima, viene a ser hallar en el mínimo tiempo posible la sorting network que caracteriza la ordenación de ese vector (por eso da igúal el tiempo de inserción suplementario a la búsqueda binaria, sólo ordenamos una vez que sabemos todas las relaciones entre elementos).

Ordenar un vector de n elementos con k vectores ordenados en su interior, el más largo de ellos de c elementos, es equivalente a ordenar los centros de de los k vectores (invocación recursiva al mismo algoritmo) y ordenar el elemento central a la izquierda del primer elemento ordenado con el central a la derecha del segundo ordenado etc… (búsqueda binaría de los centros de los k vectores en los demás de forma simultanea).

Mediante una búsqueda binaría simultanea masiva, de los elementos centrales de los k vectores, el coste sería:

ordenar(n)=(n-1)+ordenar(k)*log2(c)

En el peor caso (donde halla menos orden que aprovechar, vectores de 2 elementos)

ordenar(n)=(n-1)+ordenar( n/2)*log2(2)

P.D.: redondeando al entero superior log2(2)=1+1=2.

La idea básica la tuve este verano, pensando en dimensiones, vectores y dimensiones; ¿Si tomamos un vector como una dimensión, habría media dimensión si por ejemplo sólo coges terminos positivos? Y chorradas así.

Pero lo que de verdad importa es la siguiente idea, para ordenar N vectores ordenados, los podemos ver como N dimensiones. Por lo tanto si juntamos esos vectores en un plano N-dimensional, pudiera ser que fuera muy fácil hacer la fusión (merge) -Violeta, si algún momento lees esto, en eso es en lo que estaba pensando este verano :P-.

Para muestra un botón (uso 3 vectores, por no saber representar más de 3 dimensiones en el plano, vectores de 3 elementos para facilitar la búsqueda binaria, y son sin repetición para evitarme más problemas de momento) :

Así un algoritmo casi óptimo, adaptativo, de ordenación por comparación sería así:

Para que fuera óptimo de verdad la única variación sería comparar siempre los elementos centrales de los vectores (busqueda binaría). Siempre hacia el vector central. Sería equivalente a mi idea de un algoritmo óptimo recursivamente adaptativo.

Como se puede ver es una forma mucho más sencilla de representar y trabajar con la ordenación de vectores.

Creo que aplicando esta estructura como TAD (tipo abstracto de datos) adecuado, se pueden conseguir el numero mínimo de comparaciones para la ordenación. El TAD creo que sería un gráfo dirigido con algún añadido para localizar los centros de los vectores (también puede que sea más fácil de dibujar que n dimensiones).

Es increíble lo importante que es la busqueda binaria para desarrollar estas ideas. al fin y al cabo está en todos lados… y sino…¿Tú como cortaría el queso si quieres hacer dados con el mínimo de cortes? Por la mitad y otra vez por la mitad, hasta que los pedazos sean suficientemente pequeños.

P.D.: Le estoy dando vueltas a que puede que sea imposible hacer un algoritmo superadaptativo (recursivamente adaptativo) que a la vez sea óptimo, me da la impresión de que si comparas primero todos los centros de todos los vectores estás haciendo comparaciones que no son imprescindibles.

El algoritmo óptimo por lo tanto sería: inserción binaria del elemento central de los vectores colindantes, en el vector central, e inserción binaria recursiva de los elementos centrales de sus dos mitades, luego repetimos la operación para el resto de los vectores. Tal vez si primero ordenamos los centros de todos los vectores, nos ahorremos comparaciones, o tal vez no, y sólo fueran operaciones prescindibles, si lo implemento después de examenes, probaré las dos posibilidades.

Una pequeña discusión el la talk-page de sorting algoritms de Wikipedia, sobre un argumento que ya me dió Javifields en su día.

”

Comparison sort lower bound

I think a reference to Timsort (Python adaptive mergesort) should be done. Also, with adaptive comparison sorting algorithms in mind, I think there’s not yet a proof that log(n!) (n log n) is the best average order achievable. All that’s been proved is that worst case for any comparison sorting algorithm is n log n.

Re: Timsort. It’s certainly an interesting algorithm, particularly because it comes very close to the lower limit on the number of comparisons. The problem may be that there has been very litte scientific research into it. Tim Peters published some notes on it, but they consist mainly of benchmarks. Any article on it would be very brief, or fall foul of the “no original research” rule.

Re: O(n log n) bound. As far as I can see it’s basic information theory. Assuming n distinct keys, every comparison yields at most 1 bit of information, and that only in the case when you perform a comparison that splits the remaining permutation space exactly in two halves. So, assuming you have n! permutations with equal probability, lg(n!) comparisons on average is the absolute minimum. Grotendeels Onschadelijk 01:38, 19 August 2007 (UTC)

Re: I’m the one above. I know this basic information theory, Grotendeels, but if I’m right thats only a proof for the worst case, since by making a first sequential pass on the array you can use adaptive algorithms (even quicksort is adaptive!) to do less tan log(n!) comps. Also, an optimum alogithm, MUST do a first sequential pass on the array ( for O(n) case if ordered or inverted). Then the bound is O(n log n) ONLY if u can’t use the array pre-order. Maybe I’m wrong, but I think it’s possible to make an algorithm with an O(n log n)worst case bound, half that comparations on average, and O(n) best case. I have an idea to make it, but i’m unable to translate that to code without an enormous use of memory (at least n log(n)).Azrael60 23:28, 20 August 2007 (UTC)

Yes, it is possible to get algorithms with O(n log n) worst case. Mergesort is an example. Yes, it is possible to get O(n) for a limited number of cases. However, under the assumptions

• all keys are distinct, i.e. every comparison will give a>b or a<b, and
• the input is a random permutation, chosen uniformly from the set of all possible permutations,

it is impossible to even determine which order the input is in, in less that log₂(n!) comparisons on average.

The short argument is this: The Shannon entropy of a random permutation, distributed uniformly over all permutations of n elements is log₂(n!) bits. Since a comparison can give only two results, the maximum amount of information it can give is 1 bit. Therefore after k comparisons the remaining entropy of the permutation, given the results of those comparisons, is at least log₂(n!) - k on average. To perform the sort, we need complete information, that is, we need the remaining entropy to be 0. So we need at least k >= log₂(n!). As far as I can see I have made no worst case assumtions here, just the two assumptions noted above. Note, however, that this differs from the worst case argument, in that it does not allow rounding up to the nearest integer. For example, for n = 3, the lower bound for the worst case is 3, the lower bound for the average case as shown above is approximately 2.5849625007211561, while the highest lower bound for the average case is 8/3. Grotendeels Onschadelijk 01:18, 25 August 2007 (UTC)

I have added a slightly improved version of this argument under Comparison sort#Lower bound for the average number of comparisons. Grotendeels Onschadelijk 15:46, 25 August 2007 (UTC)”

A continuación el argumento en mayor profundidad (tendré que pensar en ello), en la página de cota mínima.

”

Lower bound for the average number of comparisons

The Shannon entropy of a random permutation, distributed uniformly over all permutations of n elements is log₂(n!) bits. Since a comparison can give only two results, the maximum amount of information it provides is 1 bit. Therefore after k comparisons the remaining entropy of the permutation, given the results of those comparisons, is at least log₂(n!) - k on average. To perform the sort, complete information is needed, so the remaining entropy must be 0. It follows that k must be at least log₂(n!).

Note that this differs from the worst case argument given above, in that it does not allow rounding up to the nearest integer. For example, for n = 3, the lower bound for the worst case is 3, the lower bound for the average case as shown above is approximately 2.58, while the highest lower bound for the average case is 8/3.

In the case that multiple items may have the same key, there is no obvious statistical interpretation for the term “average case”, so an argument like the above cannot be applied without making specific assumptions about the distribution of keys.”

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?

Microsoft (a.k.a el diablo para algúnos :P), ha sacado un entorno de desarrollo rápido de videojuegos tanto para Windows (XP, directX9) como para XBOX360. Entre otras cosas promete liberar al programador de muchas cosas feas (e innecesarias), como por ejemplo tener que escribir en cada fichero las referencias a las librerías básicas que siempre usamos (a ver si se apuntan un tanto en ADA y les copia algún IDE la idea :P).

Adiós a alguna tediosa tarea ;). Bienvenido sea, la burocracia no es buena.

Si es que, ¡todo debería de ser para torpes!

Yo pienso probarlo.

Se llama XNA Game Studio y el enlace está AQUÍ.

P.D.: A ver si otros grandes fabricantes de consolas, se ponen las pilas y empiezan a soltar SDK’s gratuitos… que es una pena que para programar algo para PSP o DS, haya que ir haciendo ingeniería inversa de todo.

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 .

Hoy quiero hablar de una de las más importantes tecnologías de la informática actual, la emulación.

Todo el mundo la usa a diario al menos por partida doble, y es que cualquier procesador (x86) actual, “emula” la arquitectura x86 sobre un conjunto de instrucciones más propios de una arquitectura RISC. La gran mayoría de estos mismos usuarios de PC también usan día a día java, que emula un procesador con su propio juego de instrucciones, el denominado “bytecode”.

La emulación nunca es perfecta, nada en informática lo es, a día de hoy, pero suele ofrecer muy buenos resultados.

Una característica interesante es por ejemplo, que el código emulado puede ser automodificable, independientemente de si la arquitectura que hay debajo lo soporta. Esto podría servir en el caso de que se requiera programar código automodificable en muchas de las arquitecturas modernas, que por motivos de rendimiento separan cachés de código y datos, y no permiten la escritura en la primera.

Pasando a una visión más divertida del asunto le recomiendo a todo el mundo con un teléfono con java (j2me, o jme que es como lo llamán ahora) , que pruebe el meBoy.

Tiene algúnos errores y otras cosas resultan incomodas, pero es lo más espectacular que he visto hasta ahora en el mundo de los emuladores. Emula juegos de gameboy, incluso gameboy color, a velocidad real, sobre cualquier movil de clase media actual (mi nokia 5200, por ejemplo). Es decir, sobre un emulador (la máquina virtual de java) corre otro (meboy) … y todo ello en un gadget del tamaño de una game boy micro. Es increible lo que pueden dar de si los ARM que llevan estos bichos.

AQUI.

Especificación y derivación de algoritmos de forma automática, algo tiene que ver con mis ideas sobre como debería de ser el programar, si lo he entendido bien, leyendo por encima.

¿Alguien sabe de estudios de derivación automática de especificaciones a código? Me interesaría muchísimo, lo veo como un gran paso de abstracción en el camino a seguir. Aunque fuera semi-automatica apoyandose en una base de datos.

EDITO: Para añadir un documento que parece aún más interesante AQUÍ.