Autoevaluación 1.4.1

Saltándome un poquito el orden, he realizado este ejercicio porque me parecía fácil y porque he obtenido un ejemplo donde se aprecia mucho la utilidad de un profiler…


He usado gprof, sobre un programa mío que consiste en aplicar la técnica de enfriamiento simulado al problema del viajante de comercio. Lo que se necesita para usar el profiler es compilar los fuentes con la opción -p, tras ejecutar el programa se crea un archivo llamado gmon.out, ahora se ejecuta la siguiente orden:
gprof nombre_Ejecutable gmon.out > kk.txt
He aplicado el programa a un problema con 575 ciudades, en kk.txt podemos ver que el programa se pasa un 88.66 % del tiempo en la función Genera_Vecino_posicion que lo que hace es dada una solución válida, obtiene otra aplicando el operador de vecino posición, esto requiere recorrer un vector entero cada se vez que se llama a la función.
La solución que he implementado es usar otro operador de vecino ( el 2-opt ) que es mucho más rápido ( consiste en intercambiar dos ciudades ) y además lo que hago es calcular primero el costo de la solución vecina y si luego me quedo con ella , es entonces cuando intercambio las posiciones de las ciudades sobre la solución actual ( esto me ahorra crear una vecino completo cada vez –> O(n) ); finalmente la generación del vecino no la he realizado en una función como estaba antes, sino desde la función donde antes se llamaba a ésta, ahorrando 575000 llamadas a función. La optimización hace que los segundos acumulados pasen de 5.95 a 0.8, lo cual no es de extrañar pues he pasado de una función O(n) ( recorrer el vector completo ) a una función de O(1) ( intercambio: 3 asignaciones ).

Anuncios

A %d blogueros les gusta esto: