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

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));
    }
}

lunes, febrero 14, 2011

Maquina Virtual en JAVA

Para crear la primera versión de una máquina virtual en lenguaje JAVA, basándonos en el modelo de Von Neumann, requerimos definir las estructuras de memoria que contendrán la lista de instrucciones a ser ejecutadas, la pila, la lista de constantes, la lista de variables y la tabla de valores de dichas variables.

Para la lista de instrucciones a ser ejecutada se crea una clase llamada Instrucción que cuenta básicamente con dos atributos, el tipo de instrucción y el índice del elemento en su respectiva tabla que va a ser operado con dicha instrucción. Los diferentes tipos de instrucción se definen con una enumeración así:

package maquinavirtual;
public enum TipoInstruccion {
    PUSH,
    vPUSH,
    nPUSH,
    STORE,
    ADD,
    SUB,
    DIV,
    MUL,
    GT,
    GE,
    LE,
    LT,
    EQ,
    NE,
    JZERO,
    GOTO,
    WRITE
}

Por su parte, la clase Instrucción queda definida de la siguiente manera:

package maquinavirtual;
public class Instruccion {
    TipoInstruccion tipo;
    int             operando;

    Instruccion(TipoInstruccion t, int op) {
        tipo=t;
        operando=op;
    }

    Instruccion(TipoInstruccion t) {
        this(t,-1);
    }

    public String toString() {
        return String.format("%-10s %d", tipo, operando);
    }
}

La clase MaquinaVirtual, definida a continuación, define un lista o vector de objetos de la clas Instruccion que representará la lista de instrucciones a ser ejecutada; una pila de objetos Double para manejar la pila; una lista de String para la lista de variables definidas; una lista de Doubles para las constantes y un Mapa de Integer y Double para manejar los valores de las diferentes variables.

Esta clase tiene dos métodos principales: el método cargarArchivo que se encarga de leer un archivo de texto que trae codificado un programa en el lenguaje de la máquina virtual y alimenta la lista de variables, la lista de constantes y la lista de instrucciones a ser ejecutadas; y por otra parte está el método ejecutar que se encarga de leer la lista de instrucciones y recorrerla ejecutándolas.

package maquinavirtual;

import java.util.*;
import java.io.*;

public class MaquinaVirtual {
    Stack<Double>                     pila = new Stack<Double>();       // Pila
    Vector<Instruccion> listaInstrucciones = new Vector<Instruccion>(); // Programa a ejecutar
    Vector<Double>      listaNumeros       = new Vector<Double>();      // Tabla de numeros
    Vector<String>      listaVariables     = new Vector<String>();      // Tabla de variables
    Map<Integer,Double> tablaVariables     = new HashMap<Integer,Double>();  // Valores de las variables

    public void mostrarValores() {
        System.out.println("\nLista de Instrucciones");
        for(Instruccion i: listaInstrucciones) System.out.println(i);
        System.out.println("\nLista de Variables");
        for(String i: listaVariables) System.out.println(i);
        System.out.println("\nLista de Numeros");
        for(Double i: listaNumeros) System.out.println(i);
    }

    public void ejecutar() {
        for(int i=0; i<listaInstrucciones.size(); i++) {
            Instruccion  inst = listaInstrucciones.elementAt(i);
            //System.out.println("Inst: " +inst);
            TipoInstruccion t = inst.tipo;
            int            op = inst.operando;
            double          a, b;
            switch(t) {
                case ADD:   b=pila.pop(); a=pila.pop(); pila.push(a+b); break;
                case SUB:   b=pila.pop(); a=pila.pop(); pila.push(a-b); break;
                case MUL:   b=pila.pop(); a=pila.pop(); pila.push(a*b); break;
                case DIV:   b=pila.pop(); a=pila.pop(); pila.push(a/b); break;
                case GT:    b=pila.pop(); a=pila.pop(); pila.push(a>b ?1.0:0.0); break;
                case GE:    b=pila.pop(); a=pila.pop(); pila.push(a>=b?1.0:0.0); break;
                case LT:    b=pila.pop(); a=pila.pop(); pila.push(a<b ?1.0:0.0); break;
                case LE:    b=pila.pop(); a=pila.pop(); pila.push(a<=b?1.0:0.0); break;
                case EQ:    b=pila.pop(); a=pila.pop(); pila.push(a==b?1.0:0.0); break;
                case NE:    b=pila.pop(); a=pila.pop(); pila.push(a!=b?1.0:0.0); break;
                case WRITE: System.out.println(pila.pop()); break;
                case nPUSH: pila.push(listaNumeros.elementAt(op)); break;
                case vPUSH: pila.push(tablaVariables.get(op)); break;
                case STORE: tablaVariables.put(op, pila.pop()); break;
                case GOTO:  i=(int) (listaNumeros.get(op)-2); break;
                case JZERO: if(pila.pop()==0.0) i=(int) (listaNumeros.get(op)-2); break;

            }
        }
    }

    public void cargarArchivo(String nombreArchivo) {
        try {
            BufferedReader in = new BufferedReader(new FileReader(nombreArchivo));
            Instruccion     inst=null;
            TipoInstruccion t=null;
            int             posicion=-1;
            while(true) {
                String linea = in.readLine();
                if(linea==null) break;
                String[] elementos = linea.trim().split("\\s+");

                try {
                    t = TipoInstruccion.valueOf(elementos[0].toUpperCase());
                    if(elementos.length==1) {
                        inst = new Instruccion(t);
                        listaInstrucciones.add(inst);
                    }
                    else if(elementos.length==2) {
                        // El segundo componente es un número
                        if(elementos[1].matches("\\d+(\\.\\d*)?")) {
                            Double numero = Double.parseDouble(elementos[1]);
                            if(!listaNumeros.contains(numero)) listaNumeros.add(numero);
                            posicion=listaNumeros.indexOf(numero);
                            if(t==TipoInstruccion.PUSH) t=TipoInstruccion.nPUSH;
                        }
                        // Si el segundo componente es una variable
                        else if(elementos[1].matches("\\p{Alpha}\\w*")) {
                            if(!listaVariables.contains(elementos[1])) listaVariables.add(elementos[1]);
                            posicion=listaVariables.indexOf(elementos[1]);
                            if(t==TipoInstruccion.PUSH) t=TipoInstruccion.vPUSH;
                        }
                        else {
                            System.err.println("Elemento desconocido: " +  elementos[1]);
                            System.exit(0);
                        }
                        inst = new Instruccion(t, posicion);
                        listaInstrucciones.add(inst);
                    }
                }
                catch(IllegalArgumentException ex) {
                    System.err.println("Error, instruccion no reconocida: " + elementos[0]);
                    System.exit(0);
                }
            }
        }
        catch(Exception x) {
            System.err.println("Error de algun tipo: " + x.getMessage());
        }
    }

}

miércoles, enero 12, 2011

Aplicaciones Web con OpenXava

De acuerdo con Wikipedia, OpenXava es un marco de trabajo de código abierto para desarrollar aplicaciones de gestión de una forma efectiva. Permite el desarrollo rápido y fácil de mantenimientos y listados pero, a su vez, es lo suficientemente flexible para desarrollar complejas aplicaciones de gestión de la vida real como contabilidad, facturación, gestión de personal, nóminas, gestión de almacenes, etc.

Actualmente OpenXava genera aplicaciones web Java (J2EE/JavaEE), que pueden ser desplegadas en cualquier portal Java (JSR-168) como una aplicación de portlets.OpenXava es una herramienta libre.

Para poder trabajar con la aplicación de demostración es necesario descargar el programa desde el sitio web  http://www.openxava.org/web/guest/home y, preferiblemente el ambiente de desarrollo de Eclipse para J2EE desde el sitio http://www.eclipse.org/downloads/

Siguiendo las instrucciones del mismo sitio web, es fácil poner en producción la aplicación web de ejemplo, así como es sorprendente ver que toda la aplicación de ejemplo queda reducida a estas dos clases en JAVA, ya que OpenXava provee automáticamente el resto:

package org.openxava.escuela.modelo;
 
import javax.persistence.*;
import org.openxava.annotations.*;
 
@Entity
public class Alumno {
    @Id @Column(length=2) @Required private int numero;
    @Column(length=40) @Required private String nombre;
    @ManyToOne @DescriptionsList private Profesor profesor;
 
    public int getNumero() { return numero; }
    public void setNumero(int numero) { this.numero = numero; }
    public String getNombre() { return nombre; }
    public void setNombre(String nombre) { this.nombre = nombre; }
    public Profesor getProfesor() { return profesor; }
    public void setProfesor(Profesor profesor){ this.profesor = profesor; }
}

package org.openxava.escuela.modelo;
 
import java.util.*;
import javax.persistence.*;
import org.openxava.annotations.*;
 
@Entity
public class Profesor {
    @Id @Column(length=5) @Required private String codigo;
    @Column(length=40) @Required private String nombre;
    @OneToMany(mappedBy="profesor") private Collection<Alumno> alumnos;
 
    public String getCodigo() { return codigo; }
    public void setCodigo(String codigo) { this.codigo = codigo;}
    public void setAlumnos(Collection<Alumno> alumnos) { this.alumnos = alumnos; }
    public void setNombre(String nombre) { this.nombre = nombre; }
    public String getNombre() { return nombre; }
    public Collection<Alumno> getAlumnos() { return alumnos; }
}


En el siguiente video se puede encontrar una breve introducción a OpenXava provista por el grupo de AltainetGroup:

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 relativ...