jueves, agosto 11, 2011

Multiprocesamiento recursivo en JAVA 7

Una de las estrategias de diseño de algoritmos más comunes es la de "divide y vencerás", en la cual, un problema de tamaño relativamente grande se divide recursivamente en problemas más pequeños que son resueltos de la misma manera hasta que se encuentre un tamaño de problema mínimo que se resuelva de forma directa. Un ejemplo típico de problemas que pueden ser resueltos con este enfoque es el algoritmo de ordenación rápida o QuickSort (ver entrada dedica a este algoritmo aquí).

En la nueva versión de JAVA se ha hecho disponible una nueva funcionalidad que permite la ejecución de algoritmos del estilo "divide y vencerás" en múltiples hilos de ejecución que son asignados entre los diferentes procesadores de la máquina. En el siguiente ejemplo se presenta una versión modificada levemente del algoritmo de ordenación rápida para utilizar esta funcionalidad:

import java.util.concurrent.*;

public class Ordenador extends RecursiveAction {
    int[] v;        // El arreglo a ordenar
    int   inicio;   // Posición inicial desde la que se va a ordenar
    int   fin;      // Posición final hasta la que se va a ordenar
    
    Ordenador(int[] x, int i, int f) {
        v      = x;
        inicio = i;
        fin    = f;
    }
    
    // Este es el método que se ejecuta cada vez que se crea un hilo de ejecución recursiva
    public void compute() {         
        if(inicio >= fin ) return ; // Cuando el arreglo tiene un elemento está ordenado y termina el proceso.
        int pivote = inicio;        // Se selecciona como pivote el primer elemnto
        int izq = inicio + 1 ;      // Apuntador izquierdo
        int der = fin ;             // Apuntador derecho
        while(izq < der) {          // Este ciclo se realiza mientras los apuntadores no se hayan cruzado
            while(izq<=fin      && v[izq]< v[pivote]) izq++;    //  Si el elemento izquierdo es menor que el pivote avanza
            while(der>=inicio+1 && v[der]>=v[pivote]) der--;    //  Si el elemento derecho es mayor que el pivote, retrocede
            if(izq < der ) {        //  Si los apuntadores no se han cruzado se intercambian los elementos derecho e izquierdo
                int tmp = v[der];
                v[der] = v[izq]; 
                v[izq] = tmp;
            }   // fin if
        }   // fin while
        // Se intercambian el valor del pivote con el valor del apuntador derecho
        int tmp   = v[der];
        v[der]    = v[pivote];
        v[pivote] = tmp;
        //  Se llaman recursivamente los objetos que van a ordenar los dos subvectores
        invokeAll(new Ordenador(v, inicio, der-1), 
                  new Ordenador(v, der+1, fin));
    }
    
    public void quickSort(int inicio, int fin) {
        if(inicio >= fin ) return ; // Cuando el arreglo tiene un elemento está ordenado
        int pivote = inicio;        // Se selecciona como pivote el primer elemnto
        int izq = inicio + 1 ;
        int der = fin ;
        while(izq < der) {
            while(izq<=fin      && v[izq]< v[pivote]) izq++;
            while(der>=inicio+1 && v[der]>=v[pivote]) der--;
            if(izq < der ) {
                int tmp = v[der];
                v[der] = v[izq]; 
                v[izq] = tmp;
            }
        }
        int tmp   = v[der];
        v[der]    = v[pivote];
        v[pivote] = tmp;
        quickSort(inicio, der-1);
        quickSort(der+1, fin);
    }
}

Para probar el uso de esta clase se crea una clase diferente que contenga el método main, así como la creación del vector y la invocación del proceso. En este programa se prueban los tiempos de ejecución obtenidos para diferentes tamaños de problema con los métodos recursivo tradicional y el nuevo método multiproceso de Java 7:

import java.util.*;
import java.util.concurrent.*;

public class TestFork {
    static Random rnd = new Random();       // Generador de números aleatorios
    // Método para crear un vector de números enteros aleatorios
    public static int[] getVector(int N) {  
        int[] v = new int[N];
        for(int i=0; i<N; i++) v[i]=rnd.nextInt(2*N);
        return v;
    }
    
    public static void main(String[] args) {
        final int MAX_SIZE = 500_000_000;
        int size = 1;                                           // tamaño del vector a crear
        System.out.println("Prueba con método recursivo tradicional");
        while(size < MAX_SIZE) {                                // Mientras el tamaño no es mayor al máximo
            int[] v = getVector(size);      
            Ordenador     ord = new Ordenador(v,0,v.length-1);  // Se crea el objeto Ordenador
            long  t1 = System.currentTimeMillis();              // Tiempo de inicio del proceso
            ord.quickSort(0, v.length-1);                       // Invocación de la ordenación con el método recursivo simple
            long  t2 = System.currentTimeMillis();              // Tiempo final del proceso
            double t = (t2-t1)/1000.0;                          // Tiempo real
            System.out.printf("%,20d %20.4f %n", size, t);      // Tamaño del vector y el tiempo requerido para ordenarlo con el viejo modelo
            size*=2;
        } // fin while
        
        System.out.println("\nPrueba con método recursivo multiproceso");
        System.out.println("Numero de procesadores disponibleS: "+Runtime.getRuntime().availableProcessors());
        size=1;
        while(size < MAX_SIZE) {                                // Mientras el tamaño no es mayor al máximo
            int[] v = getVector(size);      
            Ordenador     ord = new Ordenador(v,0,v.length-1);  // Se crea el objeto Ordenador
            long  t1 = System.currentTimeMillis();              // Tiempo de inicio del proceso
            v = getVector(size);                                // Crea un vector del mismo tamaño
            ForkJoinPool pool = new ForkJoinPool();             // Pool de procesos
            pool.invoke(ord);                                   // Invocación del pool de procesos
            long  t2 = System.currentTimeMillis();              // Tiempo final del proceso
            double t = (t2-t1)/1000.0;                          // Tiempo real
            System.out.printf("%,20d %20.4f %n", size, t);      // Tamaño del vector y el tiempo requerido para ordenarlo con el viejo modelo
            size*=2;
        } // fin while
    }
}





miércoles, agosto 03, 2011

Evaluador de expresiones en posfijo

Este programa presenta un pequeño evaluador de expresiones en posfijo que son leídas una a una. Se pretende con él dar una breve introducción al curso de Estructuras de Datos 2, y de paso, revisar las nuevas funcionalidades de JAVA 7, entre las cuales están el uso del operador diamante y la evaluación de cadenas de caracteres en la instrucción switch.

import javax.swing.*; 
import java.util.*;
public class Evaluador {
    public static void main(String[] args) {
        int n;  // número de cadenas a evaluar
        String respuesta = JOptionPane.showInputDialog("Cuántos elementos va a procesar" ); 
        n = Integer.parseInt(respuesta); 
        // Evaluar las cadenas
        for(int i=0; i<n; i++) {
            Stack<Double> pila = new java.util.Stack<>();   // Nuevo en JAVA 7 - Operador diamante
            // Leer expresion
            String expresion = JOptionPane.showInputDialog("Expresión a evaluar" ); 
            // Evaluar expresion
            expresion        = expresion.trim();        // Elimina espacios al comienzo y al final
            String[]     exp = expresion.split("\\s+"); // Para separar por secuencias de uno o más espacios
            for(String x: exp) {                        // Para cada cadena 'x' del arreglo exp
                try {
                    double valor = Double.parseDouble(x);
                    pila.push(valor);                   // Meter valor en la pila
                }
                catch(NumberFormatException ex) {       // Excepcion si la cadena 'x' no se pudo pasar a número
                    double b = pila.pop();
                    double a = pila.pop();
                    switch(x) {         // NUEVO EN JAVA 7 - Evaluación de cadenas en los switch
                        case "+"    :   pila.push(a+b); break;
                        case "-"    :   pila.push(a-b); break;
                        case "*"    :   pila.push(a*b); break;
                        case "/"    :   pila.push(a/b); break;
                    } // end switch
                } // end catch
            } // end for
            // Mostrar respuesta
            JOptionPane.showMessageDialog(null,pila.pop(), "Respuesta", JOptionPane.PLAIN_MESSAGE);
        } // end for
    }
}

martes, agosto 02, 2011

Índice TIOBE de Lenguajes de Programación para Julio de 2011

Ya se encuentra disponible el índice de popularidad de lenguajes de programación TIOBE para agosto de 2011.  La información completa se encuentra en la página http://www.tiobe.com/index.php/content/paperinfo/tpci/index.html

jueves, julio 28, 2011

Verificación de Números Vampiros

Con este programa se pretende evaluar si cuatro dígitos recibidos forman un número vampiro:

public class Test1 {
    public static void testVampiro(int d1, int d2, int d3, int d4) {
        // Este método recibe cuatro dígitos y verifica en todas las posibles parejas de números
        // si la multiplicación de dos de ellas es igual a alguno de los números que se generan
        // con los 4 dígitos
        
        int[] v = { d1, d2, d3, d4 } ; // Se crea un vector con los 4 dígitos leídos
        int[] posibles = new int[24] ; // Con 4 dígitos solo se pueden formar 24 posibles valores 
        int   cont     = 0;
        int   a,b,c;
        boolean haySolucion = false;
        
        for(int i=0; i<v.length; i++) {
            for(int j=0; j<v.length; j++) {
                if(v[i]==v[j]) continue;  // No se pueden repetir
                for(int k=0; k<v.length; k++) {
                    if(v[k]==v[i]||v[k]==v[j]) continue;    // No se puede repetir
                    for(int l=0; l<v.length; l++) {
                        if(v[l]==v[i]||v[l]==v[j]|| v[l]==v[k]) continue;   // No se puede repetir
                        posibles[cont++] = v[i]*1000+v[j]*100+v[k]*10+v[l];
                    } // fin for l
                } // fin for k
            } // fin for j
        } // fin for i
        // Para probar los numeros posibles usar esta instrucción:
        // for(int x: posibles) System.out.println(x);
        
        // Para generar las parejas se hace el siguiente ciclo:
        ciclo:
        for(int i=0; i<v.length; i++) {
            for(int j=0; j<v.length; j++) {
                if(v[i]==v[j]) continue;  // No se pueden repetir
                a = v[i]*10 + v[j];       // Se obtiene el primer valor de dos dígitos
                for(int k=0; k<v.length; k++) {
                    if(v[k]==v[i]||v[k]==v[j]) continue;    // No se puede repetir
                    for(int l=0; l<v.length; l++) {
                        if(v[l]==v[i]||v[l]==v[j]|| v[l]==v[k]) continue;   // No se puede repetir
                        b = v[k]*10+v[l];   // Se obtiene el segundo valor de dos digitos
                        c = a*b ;           // Se obtiene la multiplicación de los dos valores
                        // Se verifica si el número generado está entre los posibles resultados
                        // y de ser así se escribe la respuesta y se termina el proceso
                        for(int x: posibles) {
                            if(c==x) {
                                System.out.println("Respuesta encontrada: "+a+" x " +b+" = "+c);
                                haySolucion=true;
                                break ciclo;
                            }  // fin if
                        } // fin for x
                    } // fin for l
                } // fin for k
            } //fin for j
        } // fin for i
        if(!haySolucion) System.out.println("No hay un numero vampiro con los digitos " + d1+", "+d2+", "+d3+" y "+d4);
        
    }
    public static void main(String[] args) {
        testVampiro(1,2,3,4);
        testVampiro(1,3,9,5);
        testVampiro(3,9,1,5);
    }
}

lunes, febrero 21, 2011

Cálculo del Tiempo de Ejecución de un Método

Para facilitar el análisis de un programa, se puede utilizar una forma genérica, mediante el uso del paquete java.lang.reflect para calcular el tiempo de ejecución de cualquier función.

En este caso, el método ejecutar recibe el nombre de la clase, el nombre del método y el parámetro que recibe dicho método y retorna el tiempo que tarda el método en ser ejecutado.

import java.lang.reflect.*;

public static double ejecutar(String nombreClase, String nombreMetodo, Object parametro) throws Exception {
        double t1, t2;
        t1 = System.currentTimeMillis();
        Class    clase = Class.forName(nombreClase);
        Method  metodo = clase.getMethod(nombreMetodo,parametro.getClass());
        metodo.invoke(null, parametro);
        t2 = System.currentTimeMillis();
        return (t2-t1)/1000.0;
    }

En este ejemplo se va a calcular el tiempo requerido por el método de ordenación por inserción de la clase Algoritmos sobre un array de 10000 elementos:

public class TestEjecutar {
    public static void main(String[] args) throws Exception {
        int[] v = Algoritmos.crearVector(10000);
        System.out.println(Algoritmos.ejecutar("Algoritmos", "ordenacionInsercion", v));
    }
}

LinkWithin

Related Posts Plugin for WordPress, Blogger...

Calificar