Ordenación en serie v/s Ordenación en paralelo en Java

A menudo necesitamos ordenar la array durante la programación. Para esto, usamos el método incorporado proporcionado por Java en la clase Arrays, es decir, sort(). El método sort() utiliza la ordenación por combinación o Tim Sort para ordenar los elementos de la array. En ambos casos, el método sort() ordena secuencialmente los elementos de una array. 
En Java 8, se introdujo una nueva API para la clasificación, que es la clasificación paralela. Parallel Sort utiliza el marco Fork/Join introducido en Java 7 para asignar las tareas de clasificación a varios subprocesos disponibles en el grupo de subprocesos. Fork/Join implementa un algoritmo de robo de trabajo en el que un subproceso inactivo puede robar tareas en cola en otro subproceso. 
Por ejemplo, el siguiente código es un programa que ordena una array aleatoria de dobles usando Arrays.sort() yArrays.parallelSort() . Este programa simplemente mide la diferencia de rendimiento entre estos dos enfoques. : 

// Java program to demonstrate time taken by sort()
// and parallelSort() methods.
import java.util.Arrays;
 
public class ParallelSortTest
{
    private static final int BASE_ARRAY_SIZE = 10000;
 
    // A utility function to generate and return
    // an array of given size filled with randomly
    // generated elements.
    public static double[] generateArray(int size)
    {
        if (size <= 0 || size > Integer.MAX_VALUE)
            return null;
 
        double[] result = new double[size];
        for (int i = 0; i < size; i++)
            result[i] = Math.random();
 
        return result;
    }
 
    // Driver code to compare two sortings
    public static void main(String[] args)
    {
        for (int i = 1; i < 10000; i *= 10)
        {
            int size = BASE_ARRAY_SIZE * i;
            double[] arr1 = generateArray(size);
 
            // Creating a copy of arr1 so that we can
            // use same content for both sortings.
            double[] arr2 = Arrays.copyOf(arr1, arr1.length);
            System.out.println("Array Size: " + size);
 
            // Sorting arr1[] using serial sort
            long startTime = System.currentTimeMillis();
            Arrays.sort(arr1);
            long endTime = System.currentTimeMillis();
            System.out.println("Time take in serial: " +
                             (endTime - startTime) + "ms.");
 
            // Sorting arr2[] using serial sort
            startTime = System.currentTimeMillis();
            Arrays.parallelSort(arr2);
            endTime = System.currentTimeMillis();
            System.out.println("Time take in parallel: "
                            + (endTime - startTime) + "ms.");
            System.out.println();
        }
    }
}

Ambiente :

2.6 GHz Intel Core i7
java version "1.8.0_25"

Nota: el tiempo requerido puede variar debido a valores aleatorios en la array. Las diferencias clave entre ambos algoritmos son las siguientes: 1) Arrays.sort() : es una clasificación secuencial.

• La API usa un solo hilo para la operación.
• Lleva un poco más de tiempo realizar la operación.

2. Arrays.ParallelSort() : es una clasificación paralela.

• La API utiliza varios subprocesos para la operación.
• Es más rápido cuando hay muchos elementos, mientras que es más lento para elementos menores.

Análisis: Los resultados muestran que la clasificación paralela en una máquina multinúcleo puede lograr mejoras de rendimiento en 1 millón o más elementos. Si bien por debajo de este umbral, en realidad puede ser más lento que la clasificación secuencial. Este resultado cumple con las expectativas, y el tamaño adecuado aquí puede ser de 1 millón. Su kilometraje puede variar, depende de su entorno. Explicación: ahora, echemos un vistazo al código para descubrir cómo funciona esta clasificación paralela.

    public static void parallelSort(double[] a) {
        int n = a.length, p, g;
        if (n <= MIN_ARRAY_SORT_GRAN ||
            (p = ForkJoinPool.getCommonPoolParallelism()) == 1)
            DualPivotQuicksort.sort(a, 0, n - 1, null, 0, 0);
        else
            new ArraysParallelSortHelpers.FJDouble.Sorter
                (null, a, new double[n], 0, n, 0,
                 ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
                 MIN_ARRAY_SORT_GRAN : g).invoke();
    }

Como podemos ver, hay una granularidad mínima (java.util.Arrays.MIN_ARRAY_SORT_GRAN = 8192 [0x2000]), y si la longitud de la array es menor que la granularidad mínima, se ordena utilizando DualPivotQuicksort.sort directamente en lugar de la partición de la tarea de clasificación. Por lo general, el uso de tamaños más pequeños da como resultado una contención de memoria entre tareas que hace que las aceleraciones en paralelo sean poco probables. 
Otro juicio notable es ForkJoinPool.getCommonPoolParallelism() que devuelve el nivel de paralelismo objetivo del grupo común (de forma predeterminada, igual al número de procesadores disponibles Runtime.getRuntime(). AvailableProcessors()). Y si su máquina tiene solo 1 subproceso de trabajo, tampoco utilizará tareas paralelas. 
Cuando la longitud de la array alcanza una granularidad mínima y tiene más de 1 subproceso de trabajo, la array se ordena utilizando elmétodo de clasificación en paralelo . Y el grupo común de ForkJoin se usa para ejecutar tareas paralelas aquí. 
Referencia: http://download.java.net/lambda/b84/docs/api/java/util/Arrays.html#parallelSort%28int 
Este artículo es una contribución de Saumya Mishra . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks. Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.