LinuxParty

El algoritmo de Dios es un término que surgió en la búsqueda de aquel algoritmo que indicara los pasos mínimos que resuelven un cubo de Rubik cualquiera. El término se usa profusamente, no sólo para el cubo de Rubik.

Mucho antes de conocer dicho término, cuando me encontraba con diversos tipos de problemas, ya me asaltaba recurrentemente una pregunta irrelevante (para el caso que me ocupaba), pero que espero te haga pensar un poco en la importancia de algunas cuestiones que quizás no conoces:

“¿Qué solución daría Dios si fuera él quien resolviera el problema?”

Lo más sorprendente quizás, es que “las soluciones de Dios” no sólo no están vedadas al intelecto humano, sino que son numerosas y prolíficas. Veamosló.

Poniendo condiciones a Dios

Las metáforas con frecuencia nos ayudan a pensar (a mi sí) y la cuestión que planteo, no tiene nada que ver con la filosofía ni metafísica, la cuestión “casi” se podría haber planteado cambiando a Dios por: “el hombre más listo de la historia”, “una raza alienígena super-inteligente”, etc… usar la idea todopoderosa de Dios, es una forma inequívoca (creo) de indicar que lo que me interesa dado un problema es:

“¿cual es la solución/respuesta PERFECTA?”

Un ejemplo. Muchos conoceréis la Demoscene, si no la conoces, te estás perdiendo la fórmula 1 del códing (con permiso de SIGGRAPH). Uno de los “piques” que más me gustaban era del estilo siguiente:

“Dada una máquina concreta, con una CPU concreta, caché concreta, velocidad de reloj concreta, memoria concreta, tarjeta de vídeo concreta, sistema operativo concreto, etc… escribir un programa de no más de 4k bytes que imprima la mayor cantidad de dígitos de Pi en 30 segundos. (El valor final se calculará al promediar el resultado de 10 ejecuciones)”.

Sí, lo se, en realidad los concursos más fascinantes eran las “demos”, en lugar de calcular un aburrido Pi se trataba de crear una “intro” (¡¿tampoco sabes lo que es?!, pues corre rápido a ver algunas y fíjate en que año se hicieron y en que máquinas corrían) en tiempo real con sonido envolvente y gráficos 3D de caerse la baba. Pero he eliminado deliberadamente el aspecto subjetivo (artístico) de mi búsqueda de la solución perfecta, ¿cómo va a ser perfecta si entra en juego la subjetividad de cada uno?.

Sin embargo, la demoscene fija perfectamente las reglas que Dios también tiene que cumplir para dar la respuesta (no vale decir: “como es Dios, le pondría una DDR8 de 1Tbyte”).

El problema perfecto

Otra cosa útil de usar a Dios como metáfora, es que me sirve para cualquier tipo de problema. Cuando un arquitecto de sistemas está buscando la mejor forma de coordinar todos los recursos y flujo de información siente algo de vértigo por la cantidad de alternativas y formas de encarar el problema. Sólo cuando le das muchas vueltas, igual que aquel al que le ponen gafas nuevas, pasas de ver un borrón a ver las cosas nítidas y claras. Pero… ¿habrá otra forma mejor?. Esperas que las decisiones que tomes como mínimo no sean malas y entonces te acuerdas, “¿cómo lo habría hecho Dios?”.

Si Dios tuviera que hacer un sistema operativo para una determinada arquitectura, sin duda estaría escrito en código máquina (“A0F761B61…”), además, utilizaría los errores existentes en el hardware ¡para mejorar el sistema operativo!. Las soluciones aplicadas, serían escritas completamente “adhoc” y de una complejidad tal, que no podríamos entender absolutamente nada. Dios no utilizaría estrategias como la reutilización de código, refactorización, legibilidad, pruebas unitarias, etc… Eso sí, Dios nos daría el ISO de instalación y lo podríamos usar perfectamente (¡y sin pantallazo azul!).

Pero es curioso, y es uno de los puntos clave del post, que si a Dios le pedimos que nos minimice la expresión booleana “not ( not a + not b )” no podrá mejorar nuestra respuesta, que obviamente es “a b”, pues no hay mejor respuesta que esa. (Nota, el problema general de minimizar una expresión booleana cualquiera es NP-hard, pero ese no es el problema que hemos propuesto).

Por tanto, hay problemas en los que no podemos estar seguros de haber encontrado la solución perfecta. Pero hay otro tipo de problemas, en los que, da igual lo complejo que nos pueda parecer, sabemos seguro que obtendremos la solución perfecta.

¿No sería genial tener para todos los problemas “la solución de Dios”? (ie. el algoritmo de Dios).

La solución perfecta, de la mano de las matemáticas

Cuando hablamos de la solución perfecta, sólo hay dos posibilidades: o tenemos la solución perfecta, o no la tenemos.

Cuando tenemos la solución perfecta, ésta proviene de las matemáticas. Da igual el tipo de problema y el tipo de solución, quien únicamente puede demostrar que se trata de la solución perfecta son las matemáticas y, si no se demuestra que es la perfecta ¿cómo puedes estar seguro que no hay otra solución mejor?. (Nota: ¡cuidado!, tratar a fondo este tema es peliagudo, ie. Teorema de incompletitud de Gödel).

Ejemplos de soluciones perfectas en matemáticas son todos los teoremas demostrados y sus corolarios. Como programador no deberías ignorar (y mucho menos menospreciar) todas estas “soluciones perfectas”. En mi post anterior ya mostré como se podía reducir la típica solución de un programador (iterando) que tiene coste O(n) a una solución con coste constante O(1) usando matemáticas muy básicas (series). También en Programación lineal y entera vimos como obtener la solución perfecta de un problema más del día a día (calcular el precio de una oferta al vender libros).

Por poner otro ejemplo, en Solveet propusieron escribir una función que verifique si un número es feliz (no importa mucho si no sabes de que números se trata). La práctica totalidad de las soluciones aportadas, aplican más o menos directamente la definición, las soluciones no son malas pero el problema pide revisar números pequeños (de 1 a 500), ¿pero que pasa si los números son tan enormes que poseen millones de dígitos decimales?, ¿números como 10^1234567? (este número, escrito en un archivo de texto ocupa 1,2Mbytes), ¿sirven esas soluciones?, ¿sirven si tenemos que verificar entradas de “millones de números de millones de dígitos cada uno”?.

La cuestión es saber si esas soluciones sirven (si son la perfecta para nuestro problema).

La respuesta es, que sí sirven (aunque no son perfectas) y la demostración (de la que ahora sólo nos importa, que es matemática), es que los números felices tienen propiedades muy interesantes, una de ellas es que, para un número grande, el siguiente (al transformarlo) tiene un número exponencialmente más pequeño de dígitos.

Al reducirse exponencialmente (concretamente una cota superior es “log₁₀(81 log₁₀(81 … log₁₀(81 m) …))”) el tamaño del problema a cada transformación, aunque no sea muy eficiente, con tan sólo tres pasos, podríamos cubrir números de entorno a 10¹⁰¹⁰. ¿Cuantos de los que lo han implementado lo sabían?. (Nota: obviamente, con números tan grandes, el problema en la práctica es calcular el número de dígitos de cada tipo 1..9 que poseen, ¿sabes realmente lo grande que es el número que he escrito?).

El problema de las soluciones propuestas, es que no tienen en cuenta otra propiedad muy interesante de los números felices, y es que, la transformación de números (la suma de los cuadrados de los dígitos) mantiene invariante la felicidad de los números (si dado un número, al transformarlo tenemos un número feliz, es que es feliz; si al transformarlo tenemos un número infeliz, es que es infeliz).

El saber ésto, nos permite, dado un número máximo a chequear (eg. 10^1234567, lo cual es válido en la práctica), reducir nuestro algoritmo a ¡ocho sumas, nueve multiplicaciones y un acceso a un array!, aún hay margen para que Dios lo mejore, pero desde luego estamos muy cerca:

// Indica si un número muuuuy grande es feliz.
//   En lugar de indicar el número directamente,
//   se suponen ya contados el número de dígitos
//   que tiene.
bool IsBigHappy(
	int _1digits,
	int _2digits,
	int _3digits,
	int _4digits,
	int _5digits,
	int _6digits,
	int _7digits,
	int _8digits,
	int _9digits
) {
	return smallNumbers [
		_1digits * 1 +
		_2digits * 4 +
		_3digits * 9 +
		_4digits * 16 +
		_5digits * 25 +
		_6digits * 36 +
		_7digits * 49 +
		_8digits * 64 +
		_9digits * 81
	];
}

Aún hace falta contar sus dígitos (este problema se lo dejamos a Dios), pero sólo hace falta una vez, coste que debe añadirse al proceso anterior. (Nota: “smallNumbers” se calcula rápidamente, requiriendo únicamente 12Mbytes de memoria).

Pero en informática hay un montón de resultados útiles que provienen de las matemáticas y que generan “soluciones de Dios”, porque, pensarás que un programador pocas veces necesita checar si un número es feliz (aunque te engañas, en nuestro trabajo nos encontramos con problemas similares a diario, lo que pasa es que no tienen una definición formal). Sin embargo, utilizamos a diario directa o indirectamente los resultados “de los Dioses” como los siguientes:

• Teoría de la complejidad computacional, que permite establecer cotas a las soluciones eficientes de un problema, así, aunque no conozcamos el algoritmo de Dios, estamos seguros, de que no estamos muy lejos (o sí, lo cual es bueno también). Y sabemos ¡que ni Dios puede mejorar esa cota!.
• Teoría de la computabilidad, que permite establecer cotas a los problemas que pueden resolverse y cuales no. Es decir, ¡sabemos que ni Dios puede resolver ciertos problemas!.
• Problemas lineales de optimización, dado un problema que pueda expresarse como relaciones lineales, podemos encontrar la solución perfecta. El ejemplo más famoso es el problema del transporte de materiales entre fábricas (cuyo resultado es mucho más general y útil en nuestro día a día).
• Problemas combinacionales de optimización, en muchos casos, cuando somos capaces de obtener la respuesta, es la respuesta perfecta. El ejemplo que ya he puesto es la simplificación booleana, pero en varios post anteriores he usado este principio para obtener la solución perfecta (como en Programación lineal y entera).
• Expresiones regulares y DFA en general, con ello todos los días podemos expresar de forma fácil y eficiente, procesos que, hacerlos a mano, nos costaría un rato (eg. encontrar todas las cadenas que son de la forma “^([a-z]+)_([0-9]+)(.?)2(.?)1”).

Que no te engañe el hecho de que no ponga una lista interminable, no pretendo eso, mi objetivo es que seas tú quien busque, para tus problemas, el estado del arte actual que te permitirá utilizar la solución perfecta… disponible actualmente.

En problemas de diseño de software, de tratamiento de imágenes, bases de datos, de cálculo matemático, etc… en todos los casos, es muy probable que haya estudios, trabajos, tesis, que analizan en profundidad el estado del arte de ese tipo de problemas (ojo, no son trabajos sobre cómo hacer ésto o lo otro, son trabajos que analizan las diferentes formas que existen actualmente). Son lo más cercano que tenemos a los algoritmos de Dios, búscalos y tenlos en cuenta en tus trabajos.

Cuando la solución perfecta, no es la perfecta

Obviamente el título está mal (aunque es bonito), ya hemos dicho que una solución es o no es perfecta. Pero me sirve para destacar el hecho de que, en la práctica, en la vida real, lo primero y más fundamental, lo que todo programador debe hacer antes de poner las manos en el teclado (y es un fallo muchísimo más recurrente de lo que puedas creer), lo que uno debe analizar meticulosamente es: “¿cual es realmente el problema que tengo que resolver?”.

Suele haber muchas discusiones entorno a que lenguaje es mejor, si hay que hacer pruebas unitarias, si es mejor comentar mucho o poco, si hay que escribir un código claro o eficiente, editor de código, tipo de bases de datos, paradigma de programación, etc… uno de los motivos por el que estas discusiones levantan tanto revuelo, es porque no hay un contexto concreto sobre el que poder evaluar estrictamente la cuestión. Así, todos y ninguno tienen razón, porque depende.

Podríamos desarrollar mucho más este punto, pero lo único que quería destacar, es que la solución perfecta en un caso concreto, en un caso práctico, en un caso real, es aquella que tiene en cuenta todos los factores. ¿Habría ganado la competición de los dígitos de Pi quien la gano si en lugar de una caché L1 de 64k hubiera sido de 32k?. ¡Da igual! su problema era con una L1 de 64k y en ese momento dio con la solución perfecta.

Así, en lugar de hacer pruebas unitarias “porque dicen que es lo correcto”, piensa en cada caso si realmente forman parte de la solución perfecta o no. Por ejemplo, si estimas que codificar directamente el problema te va a llevar 60 minutos y SOLO TIENES 60 minutos, está muy claro que tu solución perfecta (si existe) pasa por ni mentar las pruebas unitarias. ¿Que nunca te has visto en esa tesitura?, me alegro por ti. (No insistas, si tienes 60 minutos para hacer algo que te cuesta 60 minutos, NO PUEDES invertir ni un segundo en otra cosa, ergo, no hay pruebas unitarias que valgan).

Cuando creas ver una solución imperfecta, pregúntate si el contexto en el que tuvo que adoptarla quien la adoptara (sí, de ese del que te estás mofando) no le obligó a ello.

La imperfecta perfecta solución

El trabajo de un programador está mucho más lleno de problemas que sí admiten una solución perfecta que los que no, lo que pasa es que muchos programadores no se paran a buscarla. Estas soluciones, en su mayor parte, pasan por aplicar resultados matemáticos. Por ejemplo, ¿que método de ordenación usarías?, Quick Sort probablemente, pero la respuesta perfecta es: “depende”, pues hay situaciones (listas pequeñas, listas cuasi-ordenadas, …) en que otros métodos son más eficientes. Un pequeño análisis estadístico de nuestros datos, puede hacernos decantar por un método u otro y obtener la solución perfecta.

En otros casos las herramientas matemáticas nos permiten ahorrar ancho de banda, número de transacciones, espacio en disco, etc… simplemente, porque hay relaciones entre los datos que procesamos y unos pueden deducirse de otros (y por tanto no hace falta llevarlos de un sitio a otro ni almacenarlos), o porque podemos deducir si la transacción es necesaria o no, encontrar invariantes (como en los números felices), etc… si habitualmente se habla de números felices, es porque son problemas más sencillos de plantear y exponer que otros (eg. encontrar un ejemplo adecuado para el post Microcódigo en mi código me llevó un buen rato).

Para aquellos problemas para los que no hay solución perfecta vete a saber lo que Dios haría, sería fascinante ver como sería el ISO/IEC 9126 de haberlo escrito Dios (mucho menos ambiguo y útil, seguro). Pero efectivamente, el flotador al que hay que agarrarse son los estándares. Sólo en ellos podemos fiarnos y por eso debemos apoyarlos.

Cuando lo pienso, una enorme cantidad de problemas que debemos de resolver los programadores son de estandarización. Si eres veterano del mundo web (por ejemplo) sabrás de lo que hablo, y si no lo eres, pregúntate porqué existen páginas como Browser Shots o porqué usar librerías intermedias (como jQuery o Lungo.js) es tan productivo (sí, también por otras cosas, pero reconoce que usar “$.inArray” quita muchos dolores de cabeza).

Los procesos que están estandarizados, no tienen porqué ser la mejor solución (¿como habría hecho Dios TCP/IP?), pero son la imperfecta perfecta solución a las que muchos damos las gracias todos los días.

Como último recurso, tenemos los patrones, la peor forma (normalmente) de solucionar un problema del que desconocemos la solución (cosa diferente es que, sabiendo la solución, estimas que lo mejor es aplicar un patrón). Más información | God’s algorithm, cubo de Rubik.
Más información | SIGGRAPH, Demoscene.
Más información | Teoría de la complejidad computacional, Teoría de la computabilidad.
Más información | Teorema de incompletitud de Gödel