Práctica 3: Diseño y Evaluación de Configuraciones :: Profiler

Profiler: NetBeans...Optimizando

Eleccion:

Voy a utilizar NetBeans porque a parte de ser Gratuito, Es de los pocos que ofrecen en el mismo IDE el profiler, ademas de ser muy completo y cómodo

Introducción:

Ante todo, he intentado no recurrir al tópico C o C++ para hacer el profiler asi que de primera pensé en PHP, no obstante no tuve mucho exito con ese lenguaje pues NetBeans no permite hacer Profiler a PHP, abandoné esta posibilidad y opté por algunas prácticas que tenía en Java, pero usaban RMI y me vi incapaz de ejecutarlas con el entorno NetBeans, por último y incapaz de abandonar asi como asi mi ganas de ser original investigue la posibilidad de crear código para movil con NetBeans pero tampoco contemplaba la opción de crear profiles, asi que me vi destinado a crear mi propio código en Java (Como he dicho abandoné desde un principio la idea de coger mis prácticas de C y C++), asi que cree todo el código que voy a mostrar en la práctica, con la ventaja de que al crearlo lo hice con el objetivo de mejorar un código hasta el orden constante.

Implementación

En principio el programa es bastante simple puesto que no es el objetivo de la práctica hacer un código muy pomposo sino entender y comprobar los profiler, asi que hice un programa en java que calcula muchas caracteristicas del número 29, cuadrado, raiz, 29^29, fibonacci...

Código: Clase Principal

/*  * To change this template, choose Tools | Templates  * and open the template in the editor.  */ package javaapplication2; /**  *  * @author Jesse  */ public class Main {     /**      * @param args the command line arguments      */               public static void main(String[] args) {         Calculos calc=new Calculos();         calc.setnumber(6);         int number=29;         int fibon=calc.fiboRecur(number),cuad,ele;         double raiz,dia;         System.out.println("El fibonacci de "+number+" es "+fibon);         cuad=calc.cuadrado(number);         System.out.println("El cuadrado de "+number+" es "+cuad);         raiz=calc.raiz(number);         System.out.println("La Raiz de "+number+" es "+raiz);         ele=calc.elevadoASiMismo(number);         System.out.println("El numero elevado a si mismo de "+number+" es "+ele);         dia=calc.diagonalCuadrado(number);         System.out.println("La diagonal del triangulo que forman dos lados de longitud "+number+" es "+dia);     } }

Código: Clase Calculos

/*  * To change this template, choose Tools | Templates  * and open the template in the editor.  */ package javaapplication2; /**  *  * @author Jesse  */ public class Calculos {     int number;     int fibos[]=new int[1000];     int ultimoCalculado=0;     public Calculos(int number){         this.number=number;     }     public Calculos(){         number=0;     }     public void setnumber(int number){         this.number=number;     }     public int fiboRecur(int numero){         //n=fibo(n-2)+fibo(n-1);         if(numero<2){            return numero;         } else{             return fiboRecur(numero-2)+fiboRecur(numero-1);         }     }         /*Esta funcion devuelve el cuadrado*/     public int cuadrado(int numero){         return numero*numero;     }         /*Esta funcion devuleve la raiz del numero*/     public double raiz(int numero){         return Math.sqrt(numero);     }     /*Esta funcion devuelve el numero elevado a si mismo*/     public int elevadoASiMismo(int number){         return (int) Math.pow((double)number,(double)number);     }     /*Esta funcion devolveria la diagonal del triangulo rectangulo formado      * por dos lados de la misma longitud: number*/     public double diagonalCuadrado(int number){         return Math.sqrt(Math.pow(number, 2)+Math.pow(number, 2));     } }

Ejecución del Programa

run:

El fibonacci de 29 es 514229

El cuadrado de 29 es 841

La Raiz de 29 es 5.385164807134504

El numero elevado a si mismo de 29 es 2147483647

La diagonal del triangulo que forman dos lados de longitud 29 es 41.012193308819754

Primer Profiler

Interpretamos el Profiler: En la imagen podemos ver los tiempos que tarda cada función del programa, lo que más resalta a la vista el el cuello de botella que produce la función fibonacci, porque tarda ella sola lo que tarda todo el programa entero, las demás son todas de orden constante luego va a ser muy dificil optimizarlas por lo que vamos a centrarnos en fibonacci: Si todo el programa tarda 3190ms fibonacci tarda 3188ms luego está claro el porqué de centrarnos en esa función

Función Fibonnaci

Como bien podemos ver en la imagen la función de fibonacci que tenemos es Recursiva y la calculamos asi fibo(n)=fibo(n-2)+fibo(n-1) con caso base n=1 y n=0, si observamos bien ese código podemos deducir que se repiten calculos (los que esten del mismo color) por ejemplo para fibo(24) que se repite varias veces en el arbol, luego podríamos mejorarlo si guardamos los resultados en un vector...

Segundo Profiler

Codigo: Fibonacci Recursiva con Guardado en Vector

public int fiboRecurMejorado(int numero){         //n=fibo(n-2)+fibo(n-1);         int fi=0;                  if(numero<2){            fi=numero;         } else if(ultimoCalculado>=numero){             fi=fibos[numero];         }else{             fi=fibos[numero]=fiboRecurMejorado(numero-2)+fiboRecurMejorado(numero-1);             this.ultimoCalculado=numero;         }         return fi;     }

Ejecucíon del profiler

Fibonacci en Concreto

En el podemos ver como se ha reducido bastante el tiempo de ejecución de fibonacci, de 3188ms a 0,307, ¡Más de 1000 veces menos!, y las invocaciones han descendido hasta un máximo de 4, no obstante sigue siendo una parte importante del programa y se puede seguir optimizando:

Tercer Profiler

Podemos intentar mejorar el fibonacci cambiando radicalmente la estrategia en la recursividad, esto lo hacemos de la siguiente forma:

• Comenzamos en el siguiente sistema de ecuaciones:


• 


• Este sistema se puede representar mediante su notación matricial como:


• 


• Conociendo a f0 = 0 y f1 = 1, al aplicar la fórmula anterior n veces se obtiene:


• 


• y más aún


• 


• Pasamos a Implementarlo

Codigo: Fibonacci Matricial

public int fiboMatricial(int numero){          int matrix[]=fiboAuxMatricial(numero);          return matrix[2];     }     public int[] fiboAuxMatricial(int num){         if(num==1){             int matrixF[]=new int[4];             matrixF[0]=0;             matrixF[1]=1;             matrixF[2]=1;             matrixF[3]=1;             return matrixF;         }else{             if(num%2==0)                 return multiRaices4(fiboAuxMatricial(num/2),fiboAuxMatricial(num/2));             else                 return multiRaices4(multiRaices4(fiboAuxMatricial(num/2),fiboAuxMatricial(num/2)),fiboAuxMatricial(1));         }     }  public int[] multiRaices4(int[] m1,int[] m2){         int aux[]=new int[4];          aux[0]=m1[0]*m2[0]+m1[1]*m2[2];          aux[1]=m1[0]*m2[1]+m1[1]*m2[3];          aux[2]=m1[2]*m2[0]+m1[3]*m2[2];          aux[3]=m1[2]*m2[1]+m1[3]*m2[3];         return aux;     }

Profiler

Como vemos no hemos mejorado nada, es más hemos empeorado asi que tenemos dos opciones, o la descartamos o la analizamos al máximo para ver los posibles fallos: Opto por la segunda.
Analizandola podemos ver una optimización bastante buena y es que en el codigo actual ejecutamos dos veces la funcion recursiva del mismo numero, pudiendo ejecutarla una vez y almacenarla en una variable, asi que lo hacemos:

Cuarto Profiler

Codigo: Fibonacci Matricial Mejorado

public int fiboMatricialMej(int numero){          int matrix[]=fiboAuxMatricialMej(numero);          return matrix[2];     }     public int[] fiboAuxMatricialMej(int num){         if(num==1){             int matrixF[]=new int[4];             matrixF[0]=0;             matrixF[1]=1;             matrixF[2]=1;             matrixF[3]=1;             return matrixF;         }else{             int matrizaux[]=fiboAuxMatricial(num/2);             matrizaux=multiRaices4(matrizaux,matrizaux);             if(num%2==0)                 return matrizaux;             else                 return multiRaices4(matrizaux,fiboAuxMatricial(1));         }     }

Java2html

Profiler

Ahora si que mejoramos lo anterior, ya solo tardamos 0,259 ms, no obstante sigue siendo una parte importante de nuestro programa y puede ser optimizada, podemos probar a hacerla iterativa, porquqe de forma iterativa consume menos recursos y tal vez podamos optimizar la función...

Quinto Profiler

Código: Fibonacci Iterativo

public int fibo(int numero){         int devuelto=0,aux1=1,aux2=0;         for(int i=1;i<numero;i++){             devuelto=aux1+aux2;             aux2=aux1;             aux1=devuelto;         }         return devuelto;     }

Profiler

De forma completamente inesperada el fibonacci iterativo arrasa con todo y tarda 0,003ms menos incluso que un sqrt, pow e incluso la inicialización de la clase, tal vez mi ordenador "digiera" mejor las sumas iterativas que los cuadrados y raices.
Podemos seguir intentado mejorarla, asi que vamos a proceder a hacer el fibonacci de orden constante que aunque en esta situación seguro que no desbanca al iterativo( porque se usan raices y cuadrados) en numeros de orden muy superior, lo desbancará seguro:

Sexto Profiler

Código: Fibonacci Constante

public int fiboConst(int numero){         double raiz5=Math.sqrt(5);         return (int)((1/raiz5)*Math.pow(((1+raiz5)/2),numero)-(1/raiz5)*Math.pow(((1-raiz5)/2),numero));     }

Profiler

Muy buen resultado: 0,96ms. Como vemos es peor que el anterior pero usando la proporción aurea podemos conseguir el orden constante y tardar 0,096ms (o un poquito mas) para cualquier número, la unica formula que hay que aplicar es esta: