PDF de programación - PROGRAMACION CONCURRENTE Ejemplos III: Sopa de Letras

PROGRAMACION CONCURRENTE

Ejemplos III: Sopa de Letras

Laura Barros

Notas:

1

Objetivo

Mostrar las diferentes estrategias que puede seguir un

gestor que tiene que ejecutar una tarea compleja que
puede ser paralelizada en diferentes subtareas, para
organizar su ejecución concurrente distribuyendo las
subtareas entre un conjunto de objetos activos que
denominamos obreros y que las ejecutan concurrentemente.

El objetivo del ejemplo es la búsqueda concurrente

en una sopa de letras de un conjunto de nombres
(JUAN, INES, CARMEN, JOSE, MARTA, CARLOS,
FELIPE, ANA, PEPE, ROSA) que se encuentran en ella
en diferentes posiciones y direcciones. El programa
debe buscar la ocurrencia de esos nombres en cualquier
dirección y los imprime en la consola indicando la
posición de la primera letra y la dirección
(LR, RL, UD, DU, DR, DL, UR, UL).

NCAHPFELIPESOMCPAPEOUJILANEVIO
VABASAEKJINESASANBPXACNAUJVANE
AAJOHAPFZAZAREKUFIATEAONIAJERA
TROSAOZAFENLCARMENPILRKAENAUIS
RPEUNAUJAPOFAERIASAADLLNPEEOCO
AUJNAAFOJSUEJAGALDAFPOAUINISOU
METUALDAOJILPDPALPMIUSULLAEOLA
EKACARLOSAUIACAOAJUANIRAENPAEG
OSJKANIIEUPLAURAIREBANOCFOTEBA
KALSSENIDSAREÑOARUALPASAEJUANS
NABAFKAGPEMMPIJAHJINESAUOSENFO
UJIAMEAAIEPDTAIFOLLADIAPLVAJHR
DAUNFOLANEHAGUEPILEFLSRNIRENZI
ELFAEPOIJUANEPSENINEIPLONEMRAC
OAYENSENPMAAPEERADFORAOMPSSCSO
RSOOAAUJAEEPHZALNAISUDSANAREEG
ANAUJAZAPAPANAFAUIUJUAINEUENIL
EHÑEJUANSAARENCARLOSDEPTAMPIAR
ASDEJUANPAATRAMEAAZAPARLNATAER
BONEINESGAAECARMENÑAPUAIPNDUAH
EFESIMANSENIADJUANFAJPAPAULATA

Procodis’09: III- Ejemplo Sopa Laura Barros

2

Notas:

2

Especificación

En el diagrama de clases de la figura se muestra la arquitectura de la aplicación basada
en tres clases.

Procodis’09: III- Ejemplo Sopa Laura Barros

3

Notas:

Clase Gestor: Existe un único objeto manager en la aplicación que es activo a través del thread del procedimiento main() de la
aplicación. El gestor carga del fichero cuyo path se recibe en su lanzamiento haciendo uso del método estático
Sopa.CargaSopa(). De forma repetida, el gestor invoca el método estático Sopa.leeNombres() y en él se queda suspendido a la
espera de que el operador introduzca la lista de nombres que quiere buscar en la sopa. El operador la introduce como una lista
de nombres separados por espacios. Por ejemplo:

Juan, Ines, Felipe, Carmen, Pepe, Juan, Luis return

El manager utilizando las diferentes estrategias que se irán proponiendo, delega en un conjunto de obreras la búsqueda de cada
una de los nombres propuestas. Espera a que todas las obreras hayan finalizado, y luego vuelve a quedar a la espera de que el
operador proponga desde el teclado una nueva lista de nombres. El manager cierra la aplicación cuando recibe del operador una
lista sin ningún nombre.
Gestor() => Constructor del objeto Gestos. De acuerdo con la estrategia de implementación, instancia todos los elementos que
se requieren para ejecutar la aplicación;
main(String[] args) => Método que lanza la aplicación. En args debe pasarse el nombre del fichero en el que se almacena la
sopa de letras.
Clase Obrero: Durante la ejecución de cada búsqueda, deberán instanciarse o estar instanciadas tantos objetos de la clase
Obrero como nombres se vayan a buscar. Cada obrero participante recibe al comienzo de la búsqueda un nombre que debe
buscar en la sopa de letras. Recorre la matriz y en cada posición haciendo uso del método estático Sopa.busca() comprueba si
en ella se inicia el nombre buscado, y por cada uno que encuentra lo escribe sobre la impresora haciendo uso del procedimiento
estático Sopa.imprime(), indicando su posición y la dirección en que se encuentra. Termina notificando al gestor de alguna
manera que ha terminado su tarea. Los obreros ofrecen diferentes interfaces de acuerdo con la estrategia que se utilice.
Clase Sopa: Constituye la infraestructura pasiva y estática en la que se encuentra almacenada la sopa de letras y a la que
acuden los obreros para buscar los nombres en la sopa, y para imprimir los resultados encontrados. Contiene el algoritmo de
búsqueda que es utilizado por los obreros para encontrar su nombre de consigna. Los procedimientos que ofrecen su interfaz
son:
static void cargaSopa(String pathOfSopaFile) => Es invocado por el manager para que lea la sopa de letras del fichero cuyo
path se pasa como parámetro.
static String[] leeNombre() => Espera que el operador introduzca una lista de nombres desde el teclado. Retorna un array de
strings con un nombre en cada elemento. Si no se introduce ningún nobre retorna un string nulo.
static void String buscaNombre( String nombre, int fila, int col) => Procedimiento reentrante que es invocado
concurrentemente por cada obrero para buscar su nombre. Busca todas las ocurrencias del nombre que se inicie en la fila y
columna que se pasan como parámetro. Retorna un mensaje que contiene el nombre, la fila, la columna, y la dirección o
direcciones en que se ha encontrado.
synchronized static void imprime(String mensaje) => Imprime en la consola el texto que se pasa como parámetro mensaje.
Es un método synchronaized, por lo que si se invoca concurrentemente, se secuencializa su ejecución.

3

Diseño I: Implementación secuencial.

El gestor realiza el proceso completo buscando en el propio thread del método principal
main() los nombres que introduce el operador.

Procodis’09: III- Ejemplo Sopa Laura Barros

4

Notas:

4

Diseño I: Código

public class Obrero {

String nombre;
Obrero(String nombre) {

}

}

}

}

this.nombre = nombre;
String s;
for (int fila = 0; fila < Sopa.dimensionMatriz(); fila++) {

for (int col = 0; col < Sopa.dimensionMatriz(); col++) {

s = Sopa.busca(nombre, fila, col);
if (s != "")
Sopa.imprime(s);

Procodis’09: III- Ejemplo Sopa Laura Barros

5

Notas:

5

Diseño I: Código

import java.io.*;
import java.util.*;
public class Gestor {

public static void main(String[] args) {

long tiempoInicial;
Sopa.cargaSopa(args[0]);
}

try {
} catch (IOException e) {
int numNombres = 1;
while (numNombres != 0) {

;

Vector<Obrero> listaObreros = new Vector<Obrero>(numNombres);
Vector<String> listaNombres = new Vector<String>();
listaNombres = Sopa.leeNombres();
tiempoInicial = System.currentTimeMillis();
numNombres = listaNombres.size();
for (int i = 0; i < numNombres; i++) {

String nombre = listaNombres.elementAt(i);
listaObreros.add(i, new Obrero(nombre));

}
System.out.println("Tiempo de ejecución: "

+ (System.currentTimeMillis() - tiempoInicial) + " ms");

}

}

}

Procodis’09: III- Ejemplo Sopa Laura Barros

6

Notas:

6

Diseño 2: Creación dinámica de los objetos obreros

El gestor una vez que ha recibido la lista de nombres que deben ser buscados, crea
dinámicamente un nuevo obrero por cada nombre, y le pasa el nombre que debe buscar a
través del constructor. Los obreros son efímeros, y se destruyen tras haber realizado la
búsqueda y su impresión. El gestor queda suspendido a la espera de que cada uno de los
obreros hayan terminado y luego vuelve a requerir al operador una nueva lista de
nombres o la orden de finalizar.

Procodis’09: III- Ejemplo Sopa Laura Barros

7

Notas:

7

Diseño 2:Diagrama de actividad

Procodis’09: III- Ejemplo Sopa Laura Barros

8

Notas:

8

Diseño 2:Diagrama de secuencias

Procodis’09: III- Ejemplo Sopa Laura Barros

9

Notas:

9

Diseño 1: ¿Modificar?

•“Los obreros son efímeros, y se destruyen tras haber realizado la búsqueda”

public class Obrero {

String nombre;
Obrero(String nombre) {

}

}

}

}

this.nombre = nombre;
String s;
for (int fila = 0; fila < Sopa.dimensionMatriz(); fila++) {

for (int col = 0; col < Sopa.dimensionMatriz(); col++) {

s = Sopa.busca(nombre, fila, col);
if (s != "")
Sopa.imprime(s);

Procodis’09: III- Ejemplo Sopa Laura Barros

10

Notas:

10

Diseño 2:Código

public class ObreroEfimero extends Thread {

String nombre;
ObreroEfimero(String nombre){

this.nombre=nombre;
this.start();
}
public void run() {

for (int fila=0;fila<Sopa.dimensionMatriz();fila++){
String s = Sopa.busca(nombre,fila,col);
if (s!="")

for (int col=0;col<Sopa.dimensionMatriz();col++){

Sopa.imprime(s);

}

}

}

}

Procodis’09: III- Ejemplo Sopa Laura Barros

11

Notas:

11

“crea dinámicamente un nuevo obrero por cada nombre”
“El gestor queda suspendido a la espera de que cada uno

Diseño 1: ¿Modificar?
•
•
de los obreros hayan terminado”
import java.io.*;
import java.util.*;
public class Gestor {

public static void main(String[] args) {

Sopa.cargaSopa(args[0]);
}

long tiempoInicial;
try {
} catch (IOException e) {
int numNombres = 1;
while (numNombres != 0) {

;

Vector<Obrero> listaObreros = new Vector<Obrero>(numNombres);
Vector<String> listaNombres = new Vector<String>();
listaNombres = Sopa.leeNombres();
tiempoInicial = System.currentTimeMillis();
numNombres = listaNombres.size();
for (int i = 0; i < numNombres; i++) {

String nombre = listaNombres.elementAt(i);
listaObreros.add(i, new Obrero(nombre));

}
System.out.println("Tiempo de ejecución: "

+ (System.currentTimeMillis() - tiempoInicial) + " ms");

}

}

}

Procodis’09: III- Ejemplo Sopa Laura Barros

12

Notas:

12

Diseño 2:Código

import java.io.*;
import java.util.*;
public class Gestor {

public static void main(String[] args) {

Collection<ObreroEfimero> obrerosCreados = new ArrayList<ObreroEfimero>();
Vector<String> listaNombres = new Vector<String>();
int numPalabras = 1;
long tiempoInicial = 0;
try {
} catch (IOException e) {
}
;
while (numPalabras != 0) {

Sopa.cargaSopa(args[0]);
System.out.println("el fichero " + "args[0]" + " no existe");

listaNombres = Sopa.leeNombres();
tiempoInicial = System.currentTimeMillis();
numPalabras = listaNombres.size();
for (int i = 0; i < numPalabras; i++) {
}
Iterator<ObreroEfimero> iter = obrerosCreados.iterator();
iter = obrerosC