Tip: MergeSort Escalable usando el API de Java
June 9th, 2007Después de hacer la comparación entre mi implementación chafa y la de Java, me quedé pensando como hacerle para reducir un poco la diferencia sin quitarle la simplicidad (más bien sin tener que aprender un QuickSort optimizado, jaja).
Entonces se me ocurrió que podría aprovechar las bondades de los, cada vez más comunes, procesadores con HT o doble núcleo. La solución es muy sencilla, solo hay que poner la mitad del arreglo en un hilo y la otra mitad, pues en otro hilo.
Pero me di cuenta de que este enfoque también es aplicable a código que utilice las librerías de Java. Solo hay que usar el método sort(int[] a, int fromIndex, int toIndex) en lugar de sort(int[] a).
De esta forma quedaría algo así para dos hilos:
new Thread() {
public void run() {
Arrays.sort(arr, 0, arr.length / 2);
}
}.start();
new Thread() {
public void run() {
Arrays.sort(arr, arr.length / 2, arr.length);
}
}.start();
Sin embargo, este código tiene un pequeño problema; cada hilo ordenará una mitad del arreglo independientemente, así que al final nuestro arreglo no estará globalmente ordenado. Por lo cual recurrí al principio del MergeSort, que se basa en combinar dos arreglos ordenados para tener como resultado un arreglo más grande tabién ordenado. Solamente necesitamos una iteración del Merge y saber donde se hizo el corte del arreglo original y todo quedará resuelto. A continuación, una versión del merge:
merge(int arr[], cuts[]) {
int index1 = cuts[0];
int index2 = cuts[1];
int src[] = arr.clone();
for (int i = 0; i < src.length; i++) {
if (index1 >= cuts[1]) {
arr[i] = src[index2++];
}
else if (index2 >= cuts[2]) {
arr[i] = src[index1++];
}
else {
if (src[index1] < src[index2]) {
arr[i] = src[index1++];
}
else {
arr[i] = src[index2++];
}
}
}
}
NOTA: El arreglo cuts contiene estos valores {0, arr.length / 2}.
Mientras estaba programando este algoritmo pensé de repente: ya que ando en esto, ¿por qué parar aquí? Debería programar algo que sirva para más que solo enteros. Así que le puse genéricos y ahora se puede ordenar cualquier colección de objetos que implementen la interfaz Comparable. Quedó un poco más lento; porque ahora se manejan colecciones y no arreglos, objetos y no tipos de datos primitivos. Pero bueno, todo sea por la cohesión balanceada.
Ya que me sentía tan espléndido, pensé: los procesadores de doble núcleo van a pasar de moda el próximo año, ¿por qué no hacemos el asunto escalable? La solución más obvia para el número de hilos que manejaría es la tendencia del número de núcleos que tienen los procesadores: 2, 4, 8, … Pero, después pensé: ¿qué tal si alguien que tiene un servidor con un montón de núcleos quiere usar mi clase? La tarea de ordenamiento consumiría todos los recursos disponibles o una fracción tal vez inadecuada. Si tengo 8 núcleos ¿qué tal si me da la gana tener a 5 ordenando, 1 para el servidor de aplicaciones, 1 para el servidor de bases de datos y otro para ver una película?
Decidí entonces hacer que aceptara cualquier número de hilos para realizar el ordenamiento. Sin embargo, esto introduce otro problema; el Merge clásico trabaja uniendo pares de arreglos. Lo cual fue resuelto ideando un Merge ad-hoc que juntase cualquier cantidad de arreglos. Lo cual tiene un poquito de overhead, pero realmente no resulta muy grave.
Finalmente, hice alguas pruebas de desempeño. Puse a ordenar 1,000 veces un Vector con 1,000,000 de objetos Integer; todo esto sobre un procesador Intel Core Duo a 1.66 Ghz. A continuación está el tiempo promedio que tardó cada implementación. Cada liga lleva al código fuente en Java.
DualSort (usa dos hilos y el Merge clásico).
ScalableSort (usando dos hilos y el Merge ad-hoc).
Collections.sort (usa un hilo, implementación de Java).
También puedes descargar un archivo JAR y usar las clases como librerías.
).