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