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

}

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