Actualmente tenemos programas que hacen un sinfín de tareas. Muchos de ellos -sino es que la mayoría- usan una interfaz gráfica para que los usuarios puedan tomar decisiones a través de botones, listas de opciones, etcétera. La interfaz gráfica se impuso por su facilidad de uso y el modo texto, o consola, fue desapareciendo poco a poco. Y aunque aún existe en los sistemas de cómputo, ya prácticamente todos los sistemas operativos utiliza una interfaz gráficaz, que se monta al arrancar el sistema y que ya está fusionado con la parte de interacción gráfica.
Pero ¿qué tanto influye la interfaz gráfica en el desempeño de un equipo de cómputo? ¿Cuántos recursos más requiere para correr un programa con relativa velocidad? Es una pregunta interesante y que a veces nos olvidamos de ello pues es claro que ahora las máquinas corren a unos 3 GHz y tienen 2, 4, 8 o más Gbytes de memoria. De hecho, cuando había computadoras de 8 bits y algunos intentos rudimentarios de interfaz gráfica (como el MousePaint de Apple //e), era claro que las limitaciones del hardware eran demasiadas. Gracias a los avances en este rubro, parece que podemos tener una hermosa interfaz gráfica con el usuario y un desempeño fenomenal, pero aunque lo parezca, no es así.
Hace unos días convoqué, vía este medio, a un reto de programación. Se trataba de hallar la secuencia más larga de números de Collatz. Hubo bastante aceptación de este “concurso” y he recibido una veintena de programas. El reto en particular era hallar la secuencia más larga en un número del 1 al millón.
Originalmente tomé mi código para calcular la secuencia de Collatz de un número y lo puse en forma de ciclo para que calculara todas las secuencias de 1 al millón. Como el programa trabajaba con una biblioteca para manejar números extremadamente grandes (más de 1000 cifras), el programa -al ejecutarse- tardaba más de diez minutos. Mi software desplegaba toda la secuencia para cada número y esto, evidentemente lo hacía muy lento. Como en el reto sólo se pide hallar la secuencia más larga, no hay necesidad de desplegar cada cálculo que la máquina hace. Así, quitando el despliegue de esta información, el programa tardaba la mitad, es decir, unos 5 minutos.
Aún así era lento. Vi programas de algunos de los participantes que tardaban menos de 15 segundos. ¿Cómo hacer para que mi programa corriera más rápido? Quité entonces la biblioteca de números grandes y usé el tipo predefinido LongInt. El programa, sin embargo, se atoraba en el número 999216. Vi la referencia y hallé que los LongInt aceptan números entre -2147483648 y 2147483647. Como algo estaba pasando, cambié las definiciones de los números a usar a LongWord, que aceptan valores entre 0 y 4294967295 y entonces mi programa corrió. Tardaba ahora alrededor de un minuto para hallar la secuencia pedida.
Pero ¿se podía ir más allá? La solución era hacer un programa que corriera sin necesidad del “overhead” que le mete la interfaz gráfica. Delphi permite crear aplicaciones que corran en modo consola/terminal. Se quita pues la sobrecarga que le impone la interfaz gráfica a todos los programas. Escribir código para aplicaciones sin interfaz gráfica es equivalente a escribir código en TurboPascal realmente. Con esto en mente, pasé mi programa más rápido a uno que no usara la interfaz gráfica. Así entonces, el programa no muestra los cálculos que hace. Sólo informa el resultado final. ¿Tiempo para hallar la secuencia más larga de Collatz? ¡Menos de 1 segundo! Sorprendente. Desde luego que estos resultados pueden variar de acuerdo a la computadora que se esté usando, pero en esencia se mantiene la misma relación de velocidades.
En conclusión, es claro que la interfaz gráfica hace muy lento, demasiado lento, el procesamiento de información. No pensaba que fuese tan grande esta sobrecarga, pero los números así lo indican.
He aquí mi código en Delphi 7 (ejecutable disponible pidiéndomelo a mi correo [email protected]):
program Collatz_Console;
{$APPTYPE CONSOLE}
uses
SysUtils;var
MaxNum : LongInt; // núm máximo
Contador : Integer;
Numero : LongWord; //núm con la secuencia más larga
Num1 : LongWord;
NuevoLong : LongWord;
NuevoCont : integer;// Números de Collatz: Encontrar la máxima secuencia usando
// LongWord en lugar de la biblioteca de números grandes
// el programa se escribió en modo consola para evitarse el
// overhead que le mete la interfaz gráficaprocedure Calcula;
begin
write(‘dame número máximo a calcular ‘);
Readln(Num1); //leo el máximo número a calcular
MaxNum := Num1;
NuevoLong := 0;
Contador := 0;
NuevoCont := 0;
repeat
repeat
if Num1 mod 2 = 0 then Num1 := Num1 div 2
else Num1 := (Num1 * 3) + 1;
inc(Contador);
until Num1 = 1;
if Contador > NuevoCont then
begin
NuevoLong := MaxNum;
NuevoCont := Contador;
end;
Contador := 0;
dec(MaxNum);
Num1 := MaxNum;
Until MaxNum = 1;
Writeln(‘Número: ‘+inttostr(NuevoLong)+ ‘ iteraciones: ‘ + inttostr(NuevoCont));
readln;
end;begin //main
Calcula
end.
Cabe señalar que hubo diferentes lenguajes en uso: Delphi, C++, C#, Ruby, Javascript, Java y Python. A pesar de ser interpretados algunos de estos lenguajes, su desempeño es estupendo, aunque me parece, no pueden competir con el compilador que genere código nativo y que además tiene, muchas veces, directivas para optimización. En este reto en particular, la velocidad para hallar la solución era el factor ganador. Sin embargo, en cualquier caso, es interesante ver el desempeño de varios de los lenguajes en boga.
Una vez dicho esto, van los resultados del reto de la secuencia más larga en los números de Collatz, de 1 a un millón:
Juan Claudio Toledo 00.029 segundos (primer lugar)
Nayely Riverón Domínguez 00.047 segundos (segundo lugar)
José Raúl Escobedo Arreola 00.053 segundos
Darío Alvarez Aranda 00.164 segundos
Fabían Vargas Quijano (*) 00.200 segundos
Carlos Torres Almonte 00.310 segundos
Kevin Reyes 00.320 segundos
Manuel López Michelone 00.420 segundos (fuera de concurso)
Luis Alfredo Juárez Blanco 00.640 segundos
Carlos Morales 00.699 segundos
Cyb3rxPuNk . 01.010 segundos
Eleazar Prieto 01.130 segundos
Ricardo Padilla Amezcua 02.324 segundos
Gerardo Robledo 03.300 segundos
Luis Rivera 05.638 segundos
Rafael Mendoza 06.540 segundos
Francisco Pérez 06.790 segundos
lugo tache 07.320 segundos
Eduardo Ruíz 07.490 segundos
David Garza 09.000 segundos
Ernesto Valderrama Blum 36.070 segundos
Roberto López Bedolla 36.350 segundos
Gabriel Romero 41.200 segundos
Rockodev 110.720 segundos
Juan Rafael Corrales más de 5 minutos
Cristian Castro Cienfuegos N/A (**)
(*) Vargas Quijano incluyó en el envío de su programa, un estudio sobre una forma de optimizar el problema para que busque de manera más inteligente. Muy interesante enfoque, sin duda.
(**) Nunca pude correr su programa. Mi sistema decía que faltaba un archivo dll que busqué, descargué y puse en mi sistema, pero jamás lo reconoció o algo extraño pasó.
El ganador del reto: Juan Claudio Toledo
Me dice Juan Claudio Toledo, que está terminando su doctorado en la UNAM, (el ganador de este reto), en el correo en donde me mandó el programa, los siguiente:
Me di cuenta que la respuesta al problema debe ser siempre > N/2. Es decir, el entero entre 1 y N con mayor ciclo debe estar en la segunda mitad del intervalo [1,N].
¿Por qué? Acá lo demuestro, por reducción al absurdo.
Sea x el entero entre 1 y N con mayor ciclo. Supongamos que x <= N/2. Puedo definir y = 2*x; como x <= N/2, tenemos que y <= N, por lo que y es también un candidato. Pero como y es par, la primera iteración del algoritmo empezando en y nos daría y/2 = x, y llegamos a x. De ahí la secuencia iría igual que si se empezara en x. Debido a esto, el ciclo de y es un paso más largo que el de x. Entonces x no es el entero de mayor ciclo, y se llega a una contradicción. Por lo tanto, x debe ser mayor que N/2.
Modifiqué el programa para que buscara a partir de N/2+1, pero me salió un tiempo más grande. La razón: estoy usando un cache para recordar los valores ya calculados, pero en este caso nunca se calculan los ciclos de números menores que N/2. Y pues esos valores se usan bastante. Empezando desde cualquier número, la secuencia debe pasar *al menos* log_2(N/2)~18 veces por números en la primera mitad.
De forma que al hacer este cambio, aunque calculo sólo la mitad de los casos, me cuesta más pues no aprovecho tanto el cache.
Así entonces, como podrán ver, esta conjetura de Collatz tiene mucha tela de donde cortar.
Con respecto al reto me gustaría hacer algunas aclaraciones:
- Los tiempos los medí en mi computadora, con un procesador AMD de seis núcleos y sistema operativo Windows 7 de 64 bits. Puede haber máquinas en donde los concursantes probaron y sus programas corrieron más rápido que lo que mi máquina reporta. Los tiempos para el reto se miden desde mi máquina.
- El fallo es inapelable. Este es un concurso hecho de buena fe, tanto por quienes participan en él como yo, quien evalúa los resultados de la manera más legal y justa posible. Aún así y para que no quede duda: los resultados son inapelables y definitivos.
- Los premios tienen como objetivo motivar a quienes quieren concursar, pero desde luego, solamente es una motivación extra. Lo importante aquí es mostrarse como un programador que puede ser mejor que los demás en eficiencia, en maneras de resolver un problema de programación.
- Cuando quise probar algunos de los programas hubo errores. Por ejemplo, no hacían correctamente el cálculo. En su momento les indiqué a los concursantes con estas dificultades sobre los problemas de su software y les pedí que me mandaran las versiones corregidas. Quienes por alguna razón no me las mandaron, simplemente quedaron fuera del reto.
- Sobre los ganadores: El primer lugar, tiene derecho a elegir el premio: la taza con el logo de La_Morsa o la tarjeta SD de 4 GB. Me pondré en contacto por correo electrónico con los ganadores para darles su premio y que me den una foto para ponerlos en la galería virtual de honor. Felicidades. La verdad me satisface mucho ver que hay tanto empuje y tan buenos programadores en este país. Me tiene muy contento eso. Agradezco la entusiasta participación y prepárense para el siguiente reto.
Los programas ganadores (el código fuente), son los siguientes:
Programa de Juan Claudio Toledo:
/************************************************************\
* collatz.cpp *
* *
* Autor: Juan C. Toledo *
* Fecha: 13 de marzo de 2013 *
* *
* Encuentra el entero entre 1 y N con el ciclo mas largo, *
* bajo el algoritmo de la conjetura de Collatz. Emplea *
* memoization para optimizar la busqueda. *
* *
* Copyright 2013 Juan C. Toledo *
* *
* Este archivo es parte de collatz. *
* *
* collatz es software libre: usted puede redistribuirlo y/o *
* modificarlo bajo los términos de la GNU General Public *
* License, publicada por la Free Software Foundation, ya sea *
* la versión 3 de la licencia, o (a su opción) cualquier *
* versión posterior. *
* *
* collatz se distribuye con la esperanza de que sea útil, *
* pero sin ninguna garantía; ni siquiera la garantía *
* implícita de comerciabilidad o idoneidad para un propósito *
* PARTICULAR. Consulte la GNU General Public License para *
* más detalles. *
* *
* Usted debe haber recibido una copia de la GNU General *
* Public License junto con Foobar. *
* Si no, véase https://www.gnu.org/licenses/ *
\************************************************************/
#include <stdio.h>int main () {
// ======================
// Configuracion
// fijar verbose a false para mejorar el tiempo de ejecucionconst int N = 1000000;
bool verbose = false;// ======================
int ciclos[N+1];
int i, pasos, maxpasos, maxnum;
long int x;// Calculamos para todos los enteros desde 1 hasta N
maxpasos = 0;
maxnum = 0;
for (i=1; i<=N; i++) {// Bucle que simula el juego
x = i;
pasos = 0;
while (x!=1){
// Si x es menor a i, ya hemos calculado su ciclo
if (x<i) { pasos = pasos + ciclos[x]; break; } if (x%2==0) x = x/2; else x = 3*x+1; pasos++; } ciclos[i] = pasos; // Actualizar maximo si ciclo es mayor if (verbose) printf(“%i: %i”,(int)i,pasos); if (pasos>maxpasos) {
maxpasos = pasos;
maxnum = i;
if (verbose) printf(” Nuevo record!”);
}
if (verbose) printf(“\n”);
}printf(“Ciclo mas largo (n<=%i): “,N);
printf(“%i con %i pasos\n”,maxnum,maxpasos);return 0;
}
La ganadora del segundo lugar: Nayely Riverón Domínguez
El código de Nayely:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>int main(void){
unsigned long tope=1000000, iteraciones=0, i=0, num=0, iteracion_mayor=0, numero_mayor=0;
int *iteraciones_totales;
printf(“Ingrese tope: “);
scanf(“%lu”,&tope);clock_t t_ini, t_fin;
double secs;
t_ini = clock();
size_t tamanyo=tope;
iteraciones_totales = (int *)malloc( tamanyo*sizeof(int) );
for(i=1;i<=tope;i++){
iteraciones=0;
num=i;
while (num > 1) {
if(num<i){
iteraciones=iteraciones_totales[num-1]+iteraciones;
num=1;
}else{
iteraciones++;
if ((num % 2) == 1){
num = 3 * num + 1;
}else{
num = num / 2;
}
}
}
iteraciones_totales[i-1]=iteraciones;
if(iteraciones>iteracion_mayor){
iteracion_mayor=iteraciones;
numero_mayor=i;
}
}
printf(“DEL 1 AL %lu\n\nNumero: %lu\nIteraciones: %lu\n\n”,tope,numero_mayor,iteracion_mayor);
t_fin = clock();
secs = (double)(t_fin – t_ini) / CLOCKS_PER_SEC;
printf(“El tiempo de calculo fue: %.16g milisegundos\n”, secs * 1000.0);
getche();
free(iteraciones_totales);
return 0;
}