Análisis y Comprobación de Algoritmos de Eficiencia en Java

danoMachine

Una vez más aportando al Foro Java, esta vez te presentamos un problema que nos permitirá hacer un Análisis de los distintos algoritmos de Eficiencia en Java, de forma eficiente e ineficiente para resolver el mismo problema. Además de esto.. se presenta una comprobación de los resultados obtenidos para demostrar la diferencia entre eficiencia e ineficiencia de éstos.

Cita:

Manual Redactado por Willymaster & EL DANO™.
©2008 Todos los Derechos Reservados para Entrebits.cl ®.
Prohibida su edición, reproducción total o parcial fuera de este sitio.

DESCRIPCIÓN GENERAL DEL PROBLEMA

La base del problema es realizar un análisis comparativo empírico de soluciones eficientes y lineales, ambos de forma iterativa, para 3 problemas que se plantean, estos son:

Calcular el k-ésimo elemento de una lista si ésta estuviera ordenada.
Calcular ab.
Buscar un valor dentro de un arreglo, si dichos elementos se hayan ordenados de mayor a menor.

Se debe crear una única clase llamada Math2, a la cual tenemos que implementar los métodos estáticos necesarios para resolver los problemas planteados.

Una vez terminada nuestra clase Math2 debemos crear una clase tipo Sistema que nos permita crear conjuntos de datos de distinto tamaño, los cuales nos permitirán obtener los tiempos resultantes para cada tipo de soluciones y así finalmente construir gráficos que nos muestren los resultados obtenidos.

DESARROLLO

La Clase Math2:

Una vez comprendida nuestra descripción del problema, comenzamos a definir nuestra clase Math2. Para solucionar el problema implementamos ocho funciones, estas son:

- La función BuscaKesimoIneficiente es la que encuentra el elemento k-ésimo, ordenando el arreglo y entregando el elemento ingresado.

- La función BuscaKesimoEficiente es la que encuentra el elemento k-ésimo en el cual usamos pivote y el método math.ceil para redondear, y construimos un ciclo para identificarlo.

- La función PotenciaIneficiente es la que encuentra el valor de la expresión pero con un tiempo de demora mayor, o sea ineficiente.

- La función PotenciaEficiente es la función que encuentra el valor de la expresión de potencia de forma más rápida, o sea la más eficiente.

- La función BuscarIneficiente es la que busca en el arreglo el número pero se demora, en conclusión es ineficiente.

- La función BuscarEficiente es la que busca dentro de un arreglo un número y lo hace rápidamente, ósea es el más eficiente.

- La función quickSort, que se invocada en la función de BuscaKesimoIneficiente, y ordena los elementos del arreglo de menor a mayor.

- La función quickSort2, que se invoca en BuscarIneficiente, y ordena los elementos del arreglo de mayor a menor.

Cofigo Fuente:

Código:

public class Math2{
    
    public static int BuscaKesimoIneficiente(int []x,int k){
        int inicio = 0;
        int[]aux;
        aux = x;
        int tope = aux.length-1;
        quickSort(aux,inicio,tope);
        return aux[k-1];
        
    }
    
    //esto funciona solo con la mediana del arreglo//
    public static int BuscaKesimoEficiente(int [] x,int k){
         int tam=x.length;
        
        // creamos el pivote y usamos el metodo math.ceil para redondear.
        
        int pivote = (int)Math.ceil(tam/2);
        int[] uno=x;
        int w=0,z=0;
        int menores=0;
        
        //creamos el ciclo para identificar el kaesimo
        while(true){
            if (tam == 1) {
                return uno[0];
            } else {
                w=z=0;
                int[] dosMenor=new int[tam-1];
                int[] dosMayor=new int[tam-1];
                for (int i = 0; i < tam; i++) {
                    if (i != pivote) {
                        if (uno[i] < uno[pivote]) {
                            dosMenor[w] = uno[i];
                            w++;
                        }
                        else {
                            dosMayor[z] = uno[i];
                            z++;
                        }
                    }                    
                }
                
                if (k == w + 1 + menores) {
                    return uno[pivote];
                }
                else {
                    if (k <= w + menores) { 
                        uno=dosMenor;
                        tam=w;
                    }
                    else {                
                        uno=dosMayor;
                        tam=z;
                        menores+=z+1;
                    }
                }
                pivote=(int)Math.ceil(tam/2);
            }
        }
    }

    
    public static int PotenciaIneficiente(int base, int Exponente) {
        int mult = 1;
        for(int i=1;i<=Exponente;i++){
            mult = base * mult;
        }
        return mult;
    }
    
    public static int PotenciaEficiente(int base,int exponente){
        int i = 0;
        int aux = base;
        if(exponente==0){
            return 1;
        }
        else{
            if(exponente == 1){
                return base;
            }
            else{
                while(i<exponente-1){
                    aux = base*aux;
                    i++;
                }
                return aux;
            }
        }
    }
    
    
    
    public static boolean BuscarIneficiente(int x[] , int numero) {
        for (int i = 0; i < x.length; i++) {
            if (x[i] == numero) {
                return true;
            } else {
                if (numero > x[i]) {
                    return false;
                }
            }
        }
        return false;
    }
    
    public static boolean BuscarEficiente(int x[], int numero) {
        int menor = 0, mayor = x.length - 1;
        int pivote;
        while (menor <= mayor) {
            pivote = (int) (mayor - menor) / 2 + menor;
            if (numero == x[pivote]) {
                return true;
            } else {
                if (numero > x[pivote]) {
                    mayor = pivote - 1;
                } else {
                    menor = pivote + 1;
                }
            }
        }
        return false;
    }
    
    private static void quickSort( int a[], int left, int right){
        int i = left;
        int j = right;
        int pivot = a[(int)(left+right)/2];
        do{
            while(a[i]<pivot)i++;
            while(a[j]>pivot)j--;
            if(i<=j){
                int aux = a[i];
                a[i] = a[j];
                a[j] = aux;
                i++;
                j--;
            }
        }while(i<=j);
        if(left<j)quickSort(a,left,j);
        if(i<right)quickSort(a,i,right);
        
    }
    
    public static void quickSort2( int a[], int left, int right){
        int i = left;
        int j = right;
        int pivot = a[(int)(left+right)/2];
        do{
            while(a[i]>pivot)i++;
            while(a[j]<pivot)j--;
            if(i<=j){
                int aux = a[i];
                a[i] = a[j];
                a[j] = aux;
                i++;
                j--;
            }
        }while(i<=j);
        if(left<j)quickSort(a,left,j);
        if(i<right)quickSort(a,i,right);
        
    }
}

La Clase Usar:

En primer lugar creamos el buffered, para leer los datos que solicitará el programa al usuario; el valor de ‘k’ para calcular el k-ésimo, el valor de ‘a’ y ‘b’ para calcular ab y un valor a buscar dentro del arreglo.

Luego implementamos un pequeño menú en el cual podemos elegir probar e algoritmo entre 1000 elementos, 10000 elementos, 100000 elementos.

Para cada caso, es decir, probando nuestras soluciones con arreglos de 1000, 10000 y 100000 elementos, haremos los siguientes pasos:

Comenzaremos con encontrar el K-ésimo elemento del arreglo, donde debemos ingresar el valor de “K”, encontrarlo dentro del arreglo de forma eficiente, usando la función BuscaKesimoEficiente de la Clase Math2, y lineal, usando la función BuscaKesimoIneficiente de la clase Math2, y luego desplegar en pantalla los tiempos transcurridos para cada tipo de solución.

En seguida debemos ingresar el valor de ‘a’ (base) y el valor de ‘b’ (exponente), calcular el valor de la potencia de forma Ineficiente, usando la función PotenciaIneficiente de la clase Math2, y eficiente, usando la función PotenciaEficiente de la clase Math2, y desplegar en pantalla los tiempos transcurridos para cada tipo de solución.

Luego se desea buscar un elemento dentro de un arreglo, aquí ingresamos el número a buscar, encontramos el elemento ingresado de manera eficiente, usando la función BuscaEficiente de la clase Math2, y de manera ineficiente, usando la función BuscaIneficiente de la Clase Math2, finalmente desplegamos en pantalla los tiempos para queda tipo de búsqueda.

Codigo Fuente:

Código:

import java.util.Vector;
import java.util.Random;
import java.io.*;

public class Usar{
    public static void main(String[]args){
        BufferedReader tld = new BufferedReader(new InputStreamReader(System.in));
        int l = 0;
        
        int[]w = new int [1000];
        Random rand1 = new Random();            
        for(int i=0;i<w.length;i++){    
            w[i] =rand1.nextInt(150000-0);
        }
        
        int[]x = new int [10000];
        Random rand2 = new Random();            
        for(int f=0;f<x.length;f++){    
            x[f] =rand2.nextInt(150000-0);
        }
        
        int[]y = new int [100000];
        Random rand3 = new Random();            
        for(int g=0;g<y.length;g++){    
            y[g] =rand3.nextInt(150000-0);
        }    
    
    do{
        
        try{
            
        System.out.println("");    
        System.out.println("1. Probar Algoritmos con 1000 elementos");
        System.out.println("2. Probar Algoritmos con 10000 elementos");
        System.out.println("3. Probar Algoritmos con 100000 elementos");
        
        int m = Integer.parseInt(tld.readLine());
            
        switch(m){
            case 1:{
                System.out.println("Ingrese el valor de K");
                int K = Integer.parseInt(tld.readLine());
                long Start = System.nanoTime();
                Math2.BuscaKesimoIneficiente(w,K);
                long End = System.nanoTime();
                long Time = End-Start;
                System.out.println("Tiempo en nanosegundos de Busqueda del K-esimo Ineficiente es "+Time );
                long Start2 = System.nanoTime();
                Math2.BuscaKesimoEficiente(w,K);
                long End2 = System.nanoTime();
                long Time2 = End2-Start2;
                System.out.println("Tiempo en nanosegundos de Busqueda del K-esimo Eficiente es "+Time2 );
                System.out.println("Ingrese La Base Para la potencia");
                int a = Integer.parseInt(tld.readLine());
                System.out.println("Ingrese El Exponente Para la potencia");
                int b = Integer.parseInt(tld.readLine());
                long Start3 = System.nanoTime();
                Math2.PotenciaIneficiente(a,b);
                long End3 = System.nanoTime();
                long Time3 = End3-Start3;
                System.out.println("Tiempo en nanosegundos de Potencia Ineficinete es "+Time3 );
                long Start4 = System.nanoTime();
                Math2.PotenciaEficiente(a,b);
                long End4 = System.nanoTime();
                long Time4 = End4-Start4;
                System.out.println("Tiempo en nanosegundos de Potencia  Eficiente es "+Time4 );
                System.out.println("Ingrese El Numero a Buscar");
                int q=Integer.parseInt(tld.readLine());
                int[]t=new int[w.length];
                for(int h=0;h<w.length;h++){
                    t[h]=w[h];
                }
                Math2.quickSort2(t,0,t.length-1);
                long Start5 = System.nanoTime();
                Math2.BuscarIneficiente(t,q);
                long End5 = System.nanoTime();
                long Time5 = End5-Start5;
                System.out.println("Tiempo en nanosegundos de Busqueda Ineficiente es "+Time5 );
                long Start6 = System.nanoTime();
                Math2.BuscarEficiente(t,q);
                long End6 = System.nanoTime();
                long Time6 = End6-Start6;
                System.out.println("Tiempo en nanosegundos de Busqueda Eficiente es "+Time6 );
                
                break;
            }
            case 2:{
                
                System.out.println("Ingrese el valor de K");
                int K = Integer.parseInt(tld.readLine());
                long Start = System.nanoTime();
                Math2.BuscaKesimoIneficiente(x,K);
                long End = System.nanoTime();
                long Time = End-Start;
                System.out.println("Tiempo en nanosegundos de Busqueda del K-esimo Ineficiente es "+Time );
                long Start2 = System.nanoTime();
                Math2.BuscaKesimoEficiente(x,K);
                long End2 = System.nanoTime();
                long Time2 = End2-Start2;
                System.out.println("Tiempo en nanosegundos de Busqueda del K-esimo Eficiente es "+Time2 );
                System.out.println("Ingrese La Base Para la potencia");
                int a = Integer.parseInt(tld.readLine());
                System.out.println("Ingrese El Exponente Para la potencia");
                int b = Integer.parseInt(tld.readLine());
                long Start3 = System.nanoTime();
                Math2.PotenciaIneficiente(a,b);
                long End3 = System.nanoTime();
                long Time3 = End3-Start3;
                System.out.println("Tiempo en nanosegundos de Potencia Ineficinete es "+Time3 );
                long Start4 = System.nanoTime();
                Math2.PotenciaEficiente(a,b);
                long End4 = System.nanoTime();
                long Time4 = End4-Start4;
                System.out.println("Tiempo en nanosegundos de Potencia  Eficiente es "+Time4 );
                System.out.println("Ingrese El Numero a Buscar");
                int q=Integer.parseInt(tld.readLine());
                int[]t=new int[x.length];
                for(int h=0;h<x.length;h++){
                    t[h]=x[h];
                }
                Math2.quickSort2(t,0,t.length-1);
                long Start5 = System.nanoTime();
                Math2.BuscarIneficiente(t,q);
                long End5 = System.nanoTime();
                long Time5 = End5-Start5;
                System.out.println("Tiempo en nanosegundos de Busqueda Ineficiente es "+Time5 );
                long Start6 = System.nanoTime();
                Math2.BuscarEficiente(t,q);
                long End6 = System.nanoTime();
                long Time6 = End6-Start6;
                System.out.println("Tiempo en nanosegundos de Busqueda Eficiente es "+Time6 );
                
                break;
                
                }
            case 3:{
                
                System.out.println("Ingrese el valor de K");
                int K = Integer.parseInt(tld.readLine());
                long Start = System.nanoTime();
                Math2.BuscaKesimoIneficiente(y,K);
                long End = System.nanoTime();
                long Time = End-Start;
                System.out.println("Tiempo en nanosegundos de Busqueda del K-esimo Ineficiente es "+Time );
                long Start2 = System.nanoTime();
                Math2.BuscaKesimoEficiente(y,K);
                long End2 = System.nanoTime();
                long Time2 = End2-Start2;
                System.out.println("Tiempo en nanosegundos de Busqueda del K-esimo Eficiente es "+Time2 );
                System.out.println("Ingrese La Base Para la potencia");
                int a = Integer.parseInt(tld.readLine());
                System.out.println("Ingrese El Exponente Para la potencia");
                int b = Integer.parseInt(tld.readLine());
                long Start3 = System.nanoTime();
                Math2.PotenciaIneficiente(a,b);
                long End3 = System.nanoTime();
                long Time3 = End3-Start3;
                System.out.println("Tiempo en nanosegundos de Potencia Ineficinete es "+Time3 );
                long Start4 = System.nanoTime();
                Math2.PotenciaEficiente(a,b);
                long End4 = System.nanoTime();
                long Time4 = End4-Start4;
                System.out.println("Tiempo en nanosegundos de Potencia  Eficiente es "+Time4 );
                System.out.println("Ingrese El Numero a Buscar");
                int q=Integer.parseInt(tld.readLine());
                int[]t=new int[y.length];
                for(int h=0;h<y.length;h++){
                    t[h]=y[h];
                }
                Math2.quickSort2(t,0,t.length-1);
                long Start5 = System.nanoTime();
                Math2.BuscarIneficiente(t,q);
                long End5 = System.nanoTime();
                long Time5 = End5-Start5;
                System.out.println("Tiempo en nanosegundos de Busqueda Ineficiente es "+Time5 );
                long Start6 = System.nanoTime();
                Math2.BuscarEficiente(t,q);
                long End6 = System.nanoTime();
                long Time6 = End6-Start6;
                System.out.println("Tiempo en nanosegundos de Busqueda Eficiente es "+Time6 );
                
                break;
                
                }        
        }
            
        }catch(IOException e){
            System.out.println("No Se Pudo Leer El Dato");
        }
        
    }while(l==1);
    

 }
}

CONCLUSIONES

Nota: De este gráfico de potencias, podemos evidenciar que en el 100% de los casos el cálculo por el método eficiente, este último predomina por sobre el ineficiente.

En el primer caso, la potencia 12 elevado a 12, el porcentaje del método de eficiencia es de un 70,36987936% por sobre el algoritmo lineal.
En el segundo caso, 10 elevado a 12, el método eficiente resulta un 37,49440716% más rápido que el ineficiente.
En el tercer caso, 15 elevado a 12, el método eficiente resulta un 41,17894737% más rápido que el ineficiente.
En el último caso, 120 elevado a 25, el método eficiente resulta un 2,858603938% más rápido que el ineficiente.

Nota: De este gráfico podemos señalar que para los distintos arreglos de prueba, siempre resultan más factibles las soluciones eficientes.

·Para el arreglo de 1000 elementos el método eficiente resulta un 89,6381653% más rápido que el ineficiente.
·Para el arreglo de 10000 elementos el método eficiente resulta un 67,36187362% más rápido que el ineficiente.
·Para el arreglo de 100000 elementos el método eficiente resulta un 73,35059179% más rápido que el ineficiente.

Nota: De este gráfico podemos recalcar que existe una gran diferencia entre los resultados de búsquedas eficientes e ineficientes, logrando un menor tiempo las búsquedas eficientes.

Para el arreglo de 1000 elementos el método eficiente resulta un 73,54236336% más rápido que el ineficiente.
Para el arreglo de 1000 elementos el método eficiente resulta un 91,96286289% más rápido que el ineficiente.
Para el arreglo de 1000 elementos el método eficiente resulta un 97,11647711% más rápido que el ineficiente.

Para finalizar podemos señalar que para calcular el K-ésimo elemento, en promedio los resultados eficientes son un 76,78354357% más rápidos que en la búsqueda ineficiente, también podemos ver que para calcular ab, los algoritmos eficientes son en promedio un 37,97545946% más rápidos que los ineficientes, y finalmente para la búsqueda del elemento los algoritmos eficientes son un 87,54056779% más eficientes que los lineales.

Esperamos que les sea de ayuda este tema.
Si te sirvió este tema danos reputación para seguir aportando,
haz click aquí ->
Saludos

Willymaster & EL DANO

moyachiche

Buen aporte cumpa! siga así ...

orivers

notable loko

danoMachine

listo, moviendo...

Willymaster

jajaja

ta wena la wea wn,

yo me pongo con el codigo fuente y tucon todo lo demas xD

Herramientas
Mostrar Versión Imprimible Enviar por Correo
Desplegado
Mode Lineal Cambiar a Modo Hibrido Cambiar a Modo Hilado

Temas Similares
Tema	Autor	Foro	Respuestas	Último mensaje
Pascal y Java: C, C++	xXx-black	Programación	3	22-oct-2008 17:16
[Capitulo I] El Lenguaje de Programación Java	danoMachine	Java	0	30-may-2008 17:47
Análizis de Algoritmos en Java	danoMachine	Java	6	25-may-2008 02:34

moyachiche Desconectado amiga Mensajes: 3.256 Agradecimientos: 1 Agradecido 73 veces en 31 mensajes Fecha de Ingreso: marzo-2007 Genero: Mujer Pais:	14-jun-2008, 17:51 Buen aporte cumpa! siga así ...

orivers Desconectado Super Moderador **** Mensajes: 4.703 Agradecimientos: 2 Agradecido 92 veces en 52 mensajes Fecha de Ingreso: diciembre-2006 Ubicación: Frente el Pc Genero: Hombre Pais:	14-jun-2008, 17:51 notable loko Mi Blog Personal

danoMachine Desconectado Gurú Mensajes: 1.344 Agradecimientos: 7 Agradecido 171 veces en 12 mensajes Fecha de Ingreso: diciembre-2007 Ubicación: en mi pieza xD Genero: Hombre Pais:	06-jul-2008, 16:42 listo, moviendo...

Willymaster Desconectado Pajarito Nuevo Mensajes: 10 Agradecimientos: 0 Agradecido 2 veces en 2 mensajes Fecha de Ingreso: junio-2008 Genero: Hombre Pais:	09-jul-2008, 01:34 jajaja ta wena la wea wn, yo me pongo con el codigo fuente y tucon todo lo demas xD