Descomposición factorial con hilos II

Descomposición factorial con hilos II
Y ahora vamos a emular un lugar donde se descomponen los números y cada vez que se encuentra uno, se obtiene y se muestra su descomposición.

Para realizar esto, usaremos los monitores de Java, los métodos wait() y notify(). Estos métodos tienen que ir siempre incluidos sobre métodos marcados como syncronized o usar el método syncronized(metodo sincronizado). wait() y notify() (hay alguno más) heredan del Object, por lo que todos los objetos que hereden de esta clase, lo tienen disponible.

¿Que hace wait()? suspende indefinidamente el hilo hasta que se reanude con notify().

Así que crearé una clase que solicitará la descomposición del número, el cual es enviado al supuesto servidor compartido de descomposiciones factoriales, este se encarga de descomponerlo (tarea dura) y una vez que termine, habrá un receptor de datos esperando a su finalización para mostrar su descomposición.

DESC

La clase SolicitudDescomposicionVisualizadorDescomposicion heredan de Thread, los iniciamos desde la clase principal y a trabajar por parte del servidor. He aquí el código:

public static void main(String[] args) {
        // TODO code application logic here
        
        ServidorDescomposicion r=new ServidorDescomposicion();
        for (int i = 0; i < 10; i++) {
            SolicitudDescomposicion productor=new SolicitudDescomposicion(i, r);
            VisualizadorDescomposicion consumidor=new VisualizadorDescomposicion(i, r);
            
            productor.start();
            consumidor.start();
        }
        
    }
public class SolicitudDescomposicion extends Thread {
    
    ServidorDescomposicion r;
    
    public SolicitudDescomposicion(int n, ServidorDescomposicion _r){
        this.setName("Productor " + n);
        r=_r;
    }
    
    @Override
    public void run(){
        int n=Math.abs(new Random().nextInt());
        System.out.println("Enviando número descomposición desde el productor:\t" + n);
        r.descomponerNumero(n);
    }
}

public class VisualizadorDescomposicion extends Thread{
    
    ServidorDescomposicion r;
    
    public VisualizadorDescomposicion(int n, ServidorDescomposicion _r){
        this.setName("Consumidor " + n);
        r=_r;
    }
    
    @Override
    public void run(){        
        String desc="";
        try {
            desc = r.getDescomposicion();
        } catch (InterruptedException ex) {
            Logger.getLogger(VisualizadorDescomposicion.class.getName()).log(Level.SEVERE, null, ex);
        }
        System.out.println("Datos obtenidos desde el consumidor.Resultado:\t\t" + desc);        
    }
}
public class ServidorDescomposicion {

    ArrayList buffer;
    boolean existData;


    //&& estado.equals(estadoEnum.DESCOMPONIENDO
    //&& estado.equals(estadoEnum.LIBRE)
    public ServidorDescomposicion() {
        buffer = new ArrayList();
    }

    public synchronized void descomponerNumero(int numero) {
        descomponer(numero);
    }

    void retardo(int ms) {
        try {
            Thread.sleep(ms);
        } catch (InterruptedException ex) {
            Logger.getLogger(ServidorDescomposicion.class.getName()).log(Level.SEVERE, null, ex);
        }
    }

    public synchronized String getDescomposicion() throws InterruptedException {
        
        while(!existData){
            try {
                wait();
            } catch (InterruptedException ex) {
                Logger.getLogger(ServidorDescomposicion.class.getName()).log(Level.SEVERE, null, ex);
            }
        }
        
        String descomposicion = "";
        descomposicion = buffer.remove(0);
        if (buffer.size()==0) {
            existData=false;
        }
        notify();
        
        return descomposicion;
    }

    void descomponer(int numero) {
        // Cálculos y resultados
        int iniNum = numero;
        int numeroAux = numero;
        int n = 0;
        int nn = 0;

        String text = "";
        String puntos = ".";

        for (long i = 2; i < numero; i++) { 
            while (numeroAux % i == 0) {
                numeroAux /= i;
                text += i + ".";
                if (numeroAux == 1) {
                    numero = numeroAux;
                }
            }
        }
        if (text.isEmpty()) {
            System.out.printf("El número %s es primo!\n", iniNum);
            text = String.valueOf(iniNum);
        }
        buffer.add(String.format("%s=%s", iniNum, text));
        existData=true;

    }

}

y el resultado para 10 números enteros


Enviando número descomposición desde el productor:	1007666687
Enviando número descomposición desde el productor:	233955388
Enviando número descomposición desde el productor:	403028651
Enviando número descomposición desde el productor:	1405658987
Enviando número descomposición desde el productor:	809322159
Enviando número descomposición desde el productor:	263332588
Enviando número descomposición desde el productor:	1552584352
Enviando número descomposición desde el productor:	1342709543
Datos obtenidos desde el consumidor.Resultado:		1007666687=17.31.43.53.839.
Datos obtenidos desde el consumidor.Resultado:		1342709543=7.191815649.
Datos obtenidos desde el consumidor.Resultado:		1552584352=2.2.2.2.2.11.89.49559.
Datos obtenidos desde el consumidor.Resultado:		263332588=2.2.487.135181.
Datos obtenidos desde el consumidor.Resultado:		809322159=3.113.733.3257.
Datos obtenidos desde el consumidor.Resultado:		403028651=67.6015353.
Datos obtenidos desde el consumidor.Resultado:		233955388=2.2.31.443.4259.
Datos obtenidos desde el consumidor.Resultado:		1405658987=127.199.55619.

Saludos

Anuncios

Descomposición factorial con hilos I

Descomposición factorial con hilos I

Un ejemplo de aprovechamiento de recursos sobre procesos penosos en los que ponemos el pc a prueba, puede ser la descomposición de números grandes en factores primos. En este ejemplo sobre la plataforma Java, se descomponen números del tipo Long con un método estándar (no muy eficiente) con una clase que implementa la Interfaz Runnable. A la clase le pasamos un número como parámetro y otro de identificador.Si creamos varios hilos, cada uno descomponiendo un número grande, aprovechará los distintos núcleos para el cálculo. Este es el resultado para números enteros pequeños mostrando el número de hilos vivos.

INICIO Hilo nº0-> Descomposición de 1763458
INICIO Hilo nº2-> Descomposición de 882375341
INICIO Hilo nº3-> Descomposición de 396209470
INICIO Hilo nº1-> Descomposición de 1633289887
Hilo nº 0-> Descomponiendo 1763458. Nº iteraciones: 1
Hilo nº 2-> Descomponiendo 882375341. Nº iteraciones: 96
Hilo nº 3-> Descomponiendo 396209470. Nº iteraciones: 1
Hilo nº 3-> Descomponiendo 198104735. Nº iteraciones: 4
Hilo nº 3-> Descomponiendo 39620947. Nº iteraciones: 18
Hilo nº 3-> Descomponiendo 2085313. Nº iteraciones: 210
Hilo nº 1-> Descomponiendo 1633289887. Nº iteraciones: 66
Hilo nº 1-> Descomponiendo 24377461. Nº iteraciones: 100
Hilo nº 3-> Descomponiendo 9883. Nº iteraciones: 9882
FIN Hilo nº 3-> 396209470 = 2*5*19*211*9883*. Nº iteraciones: 9882
Quedan 3 hilos vivos
Hilo nº 2-> Descomponiendo 9096653. Nº iteraciones: 1810
Hilo nº 2-> Descomponiendo 5023. Nº iteraciones: 5022
FIN Hilo nº 2-> 882375341 = 97*1811*5023*. Nº iteraciones: 5022
Quedan 2 hilos vivos
Hilo nº 1-> Descomponiendo 241361. Nº iteraciones: 241360
FIN Hilo nº 1-> 1633289887 = 67*101*241361*. Nº iteraciones: 241360
Quedan 1 hilos vivos
Hilo nº 0-> Descomponiendo 881729. Nº iteraciones: 881728
FIN Hilo nº 0-> 1763458 = 2*881729*. Nº iteraciones: 881728
Quedan 0 hilos vivos

Y el código de las clases…

Clase Main

package Descompositor;

import java.util.Random;

// <editor-fold defaultstate="collapsed" desc="Cabecera de clase">
/******************************************************
 *  @author:    Joaquín Martínez Rus (c) 2017
 *  @version:   1.0
 *  File:       Main.java
 *  Created:    29/11/2017
 *  Project:    PSP. Ejemplo de descomposición multihilo.
 *  Comments:
 *******************************************************/
// </editor-fold>
public class Main {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here
        for (int i = 0; i < 5; i++) {
            Descomposicion d=new Descomposicion(Math.abs(new Random().nextLong()),i);
            Thread hilo=new Thread(d);
            hilo.start();
        }
    }
}

y la clase encargada de la descomposición

package Descompositor;
import java.util.Date;
// <editor-fold defaultstate="collapsed" desc="Cabecera de clase">
/******************************************************
 *  @author:    Joaquín Martínez Rus (c) 2017
 *  @version:   1.0
 *  File:       Descomposicion.java
 *  Created:    29/11/2017
 *  Project:    PSP. Ejemplo de descomposición multihilo.
 *  Comments:
 *******************************************************/
// </editor-fold>
public class Descomposicion implements Runnable{

    public Descomposicion(long n, int j){
        this.name=j;
        this.number=n;
        Descomposicion.instanciasVivas++;
    }

    public static int instanciasVivas;
    int name;
    long number;

    @Override
    public void run() {
        descomponer(number, name);
    }

    void descomponer(long numero, int j){
        // Cálculos y resultados

        long iniNum=numero;
        long numeroAux = numero;
        long n=0;
        int nn=0;

        System.out.printf("INICIO Hilo nº%s-> Descomposición de %s\n" , j, numeroAux);
        String text="";
        String puntos=".";

        for (long i = 2; i 1000000000) {
                nn++;
                String cadena="Hilo Nº %s-> Seguimos calculando para %s...\n";
                if (nn>2) {
                    if (text.isEmpty()) {
                        cadena = "Hilo Nº %s-> parece que el número %s es primo...\n";
                    }
                    else{
                        cadena ="Hilo Nº %s-> No es primo y seguimos calculando para %s...\n";
                        nn=0;
                    }
                }
                System.out.printf(cadena, j, numeroAux);
                n=0;

            }
            // DESCOMPOSICIÓN
            while (numeroAux % i == 0) {
                System.out.printf("Hilo nº %s-> Descomponiendo %s. Nº iteraciones: %s\n",j, numeroAux, n);
                numeroAux /= i;
                text += i + "*";
                if (numeroAux == 1) {
                    numero=numeroAux;
                }
            }
        }
        if (text.isEmpty()){
            System.out.printf("El número %s es primo!\n",iniNum);
            text = String.valueOf(iniNum);
        }
        System.out.printf("FIN Hilo nº %s-> %s = %s. Nº iteraciones: %s\n",j, iniNum, text, n);

        Descomposicion.instanciasVivas--;
        System.out.printf("Quedan %s hilos vivos\n",Descomposicion.instanciasVivas);

    }
}

Os adjunto el proyecto de NetBeans.

Saludos

 

Distancia de Levenshtein

Distancia de Levenshtein

La distancia de Levenshtein es el número mínimo que necesitamos para convertir una palabra en otra, un ejemplo pelo y perro tienen tienen una distancia de 2 porque tendríamos que sustituir la l por una r y añadir una r, dos movimientos, distancia 2. Otro ejemplo, murcielago y muerdago que tienen una distancia de 5, ya que a murciélago le tenemos que quitar c,i,e,l y a muerdago le quitamos la d, por tanto necesitamos 5 movimientos para convertir una palabra en otra. Resumiendo, cuanto más pequeña sea la distancia, más parecidas son las dos palabras.

¿Esto para que sirve?, pues muy fácil, para obtener palabras similares en los buscadores o mostrar palabras alternativas por ejemplo. Vamos a ver el algoritmo y como funciona.

Este algoritmo es una matriz de n filas por m columnas donde n y m son el número de caracteres + 1 de cada palabra. El primer paso que se realiza es rellenar la primera fila y la primera columna con números secuenciales de 0 hasta n+1 y desde 0 hasta m+1 , quedando del siguiente modo para el caso del ejemplo inicial la matriz de 11×9:

levensthein0Una vez tenemos la matriz inicial, empezaremos a realizar comparaciones por filas de cada caracter con el caracter de cada columna. En cada operación, obtenemos primero el peso y tres valores de los cuales deduciremos el menor de ellos como valor final y con un ejemplo lo veremos mejor.

Comenzamos comparando los caracteres, la letra “m” de murcielago (en la columna), lo comparamos con la “m” de muerdago (filas), si es el mismo caracter se le asigna un peso de 0 y si es diferente, le asignamos 1, en este caso como son iguales, le asignamos un 0. A continuación obtenemos los tres valores, el primero con la casilla superior sumándole al valor de esta un 1, en este caso 1+1=2, el siguiente con la casilla que está situada a su izquierda haciéndolo de igual modo, 1+1=2 y por último a la casilla superior izquierda, la que está situada en la diagonal a la que le sumaremos el valor del peso, 0+0=0; de estos tres valores, cogeremos el menor que en este caso es el 0. levensthein1

Vamos a por el siguiente, peso igual a 0, porque u es igual a u, por la izquierda, 0+1=1, la diagonal 1+0=1 y la superior 1+2=2, el mínimo de los tres es 1

levensthein2

continuando con las comparaciones y obtención del mínimo, quedaría nuestra matriz completa del siguiente modo:

levensthein3

El último valor, es la distancia de Levenshtein, en este caso es 5, si quisieramos ver la proporción de acierto, deberíamos obtener la la diferencia con la unidad de la relación entre la distancia y el número de caracteres del mayor en este caso, 1 – (5/10)=0,5 o 50%. La distancia de “murcielago” y “cerro muriano” es de 10, por tanto 1-(10/13)=0.2308 o del 23,08%.

El algoritmo implementado con lenguajes de programación no tiene ningún misterio para el que esté acostumbrado a las matrices, además en Wikipedia, podéis encontrar su implementación en diferentes lenguajes, por ejemplo en php ya tiene una función como tal.

vladimir-levenshtein¿Que utilidades podemos darle? por ejemplo palabras sugerentes en base a un diccionario o aproximaciones, corrección de ortografía, etc. y además, existen variantes del algoritmo como la de Damerau-Levenshtein, otros más complejos, algoritmos fonéticos.

Este algoritmo se lo debemos a Vladimir Levenshtein, un matemático ruso que lo desarrolló en 1965.

He hecho en C# una app de consola como muestra para obtener la matriz y en base a un diccionario, nos muestre sugerencia de palabra.  levensthein4

levensthein5