Algoritmo en Paralelo
Nuestro algoritmo en paralelo se basará en una aplicación practicada durante investigaciones policiales, la identificación mediante ADN. Nosotros nos enfocaremos en algo más básico y simple, buscar una secuencia determinada sobre una representación de una cadena de ADN. Para ello utilizamos un archivo de texto con la parte entera y 7000 decimales del número PI.Método principal "main"
- Inicio
- Seleccionar archivo
- Leer el contenido del archivo y almacenarlo en cadena(String)
- Ingresa la secuencia a buscar y almacenarlo en find(String)
- Dividir la longitud del contenido del archivo entre 300 (generar valor flotante y almacenarlo en calc)
- Comparar si calc es mayor a la cantidad entera mas 0.5, entonces, completar la cifra a un entero, este nuevo valor se almacena en N (int) y almacenar 0 en la variable vDec(int)
- Si el paso anterior fue falso, se elimina el valor flotante para quedar como entero, almacenar este valor en N (int) y almacenar el valor decimal en vDec(int)
- Generar N ciclos y dentro de cada ciclo, instanciar un hilo de la clase Buscador y enviar como parametros en el constructor N, vDec, find, cadena y el numero de ciclo actual
- Generar N ciclos hasta que el metodo finish de cada uno de los hilos instanciados, regrese el valor true
- Imprimir lo regresado por el metodo getMessages de cada uno de los hilos instanciados
- Fin
Diagrama de flujo
Algoritmo correspondiente al hilo
- Inicio
- Almacenar el valor false, en la variable boolean bandera
- Almacenar el primer valor recibido por el contructor en la variable total(int)
- Almacenar el segundo valor recibido por el contructor en la variable parcial(int)
- Almacenar el tercer valor recibido por el contructor en la variable buscar(String), calcular su longitud y almacenarlo en lB(int)
- Almacenar el cuarto valor recibido por el contructor en la variable Cadena(String), calcular su longitud y almacenarlo en lC(int)
- Multiplicar el quinto valor recibido por el constructor por 300 y almacenarlo en la variable init(int)
- Si el valor de parcial, es diferente de 0, hacer la operacion 300*(parcial/100) + init*300; y guardar el resultado en TotalCiclos
- Hacer un ciclo infinito
- Generar total de ciclos, iniciando una variable int i en init - 1, terminar los ciclos hasta TotalCiclos - 1. Dentro del ciclo, iniciar otro ciclo, iniciando en int x = 0 y terminar hasta LB - 1, iniciar tambien una variable indicador (int) en 0 y la variable pos(int) = 0
- Dentro de ambos ciclos, comparar si el caracter i de Cadena, es igual al caracter x de buscar, si es igual, ir al siguiente paso, en caso contrario, almacenar 0 en indicador y 0 en pos
- Comparar si la variable indicador es igual a cero, si es asi, almacenar i en pos y sumar 1 a indicador
- Posterior al incremento de indicador, comparar si indicador es igual a lB, si es asi, guardar true en bandera y romper los ciclos de x e i
- Comparar si pos es diferente de 0, si es asi, guardar "Cadena encontrada en la posicion " init + pos, en la variable mensaje, en caso contrario, guardar "No se encontraron coincidencias" e la variable mensaje
- Fin
Diagrama de flujo
En ejecución
Secuencial
En Paralello
Resultados de la ejecución en programación secuencial
Resultados de la ejecución en programación en paralelo
Contrariamente al secuencial aquí la variación fue de unidad, solo hasta 4 milisegundos.
Conclusiones
La búsqueda de subsecuencias sobre contenido de larga extensión puede resultar más eficiente si la tarea se divide en segmentos, como la paralelización. Sin embargo recordemos que también influyen las características del hardware, esto debido a que las pruebas fueron efectuadas en dos ordenadores con diferentes características.
La identificación de subsecuencia, refiriéndose al ADN, no sirve simplemente en los casos criminales. También para encontrar regiones específicas encargadas de procesos biológicos, así como alteraciones en dichos segmentos.
