java - recursive - Multiproceso, quicksort o mergesort

mergesort c++ codigo

Question

¿Cómo puedo implementar un algoritmo quicksort o mergesort concurrente para Java?

Tuvimos problemas en una Mac de 16 (virtuales) donde solo funcionaba un núcleo (!) Usando el algoritmo de ordenación predeterminado de Java y, bueno, no era bueno ver que una máquina muy fina fuera completamente infrautilizada. Así que escribimos el nuestro (lo escribí) y obtuvimos buenas aceleraciones (escribí un quicksort multiproceso y debido a su naturaleza de particionamiento se paraleliza muy bien, pero podría haber escrito un mergesort también) ... Pero mi implementación solo escala hasta 4 hilos, es un código propietario, y prefiero usar uno proveniente de una fuente acreditada en lugar de usar mi rueda inventada.

El único que encontré en la Web es un ejemplo de cómo no escribir una conexión rápida de subprocesos múltiples en Java, es ocupado-looping (que es realmente terrible) usando un:

while (helpRequested) { }

http://broadcast.oreilly.com/2009/06/may-column-multithreaded-algor.html

Así que, además de perder un hilo sin ninguna razón, es asegurarse de matar los perfs por ocupado bucle en ese ciclo while (que es alucinante).

De ahí mi pregunta: ¿conoces alguna implementación de multiprocesamiento rápido o mergestort en Java que proceda de una fuente acreditada?

Puse el énfasis en el hecho de que sé que la complejidad se mantiene en O (n log n), pero aún disfrutaría mucho ver que todos estos núcleos comienzan a funcionar en lugar de funcionar al ralentí. Tenga en cuenta que para otras tareas, en los mismos 16 núcleos virtuales Mac, vi una aceleración de hasta x7 paralelizando el código (y no soy un experto en concurrencia).

Así que incluso si la complejidad se mantiene en O (n log n), realmente apreciaría una aceleración x7 o x8 o incluso x16.

Answer 1

¿Por qué crees que un tipo paralelo ayudaría? Creo que la mayoría de las clasificaciones están unidas, no procesadas. A menos que su comparación haga muchos cálculos, una aceleración es poco probable.

Answer 2

Acabo de codificar el MergeSort anterior y el rendimiento fue muy pobre.

El bloque de código se refiere a "coInvoke (izquierda, derecha);" pero no hubo referencia a esto y lo reemplazó con invokeAll (izquierda, derecha);

El código de prueba es:

MergeSort mysort = new MyMergeSort(array,0,array.length);
ForkJoinPool threadPool = new ForkJoinPool();
threadPool.invoke(mysort);

pero tuvo que detenerlo debido a un bajo rendimiento.

Veo que el artículo anterior tiene casi un año y tal vez las cosas han cambiado ahora.

He encontrado el código en el artículo alternativo para trabajar: http://blog.quibb.org/2010/03/jsr-166-the-java-forkjoin-framework/

Answer 3

He estado enfrentando el problema de género multiproceso los últimos días. Como se explica en esta diapositiva de Caltech, lo mejor que puede hacer simplemente con subprocesamiento múltiple en cada paso de la división y conquistar enfoques sobre el número obvio de subprocesos (el número de divisiones) es limitado. Supongo que esto se debe a que, si bien puedes ejecutar 64 divisiones en 64 subprocesos usando los 64 núcleos de tu máquina, las 4 divisiones solo se pueden ejecutar en 4 subprocesos, el 2 en 2 y el 1 en 1, etc. Por lo tanto, para muchos niveles de la recursión su máquina está infrautilizada.

Anoche se me ocurrió una solución que podría ser útil en mi propio trabajo, así que la publicaré aquí.

Iff, el primer criterio de tu función de clasificación se basa en un número entero de tamaño máximo s, ya sea un número entero real o un carácter en una cadena, de modo que este número entero o char define completamente el nivel más alto de tu género, entonces creo que hay una solución muy rápida (y fácil). Simplemente use ese número entero inicial para dividir su problema de clasificación en problemas de clasificación más pequeños, y ordene los que utilizan el género de ordenamiento de un solo subproceso que usted elija. La división en clases s se puede hacer en una sola pasada, creo. No hay problema de fusión después de hacer los géneros independientes, porque ya sabes que todo en la clase 1 se ordena antes de la clase 2, y así sucesivamente.

Ejemplo: si desea hacer una ordenación basada en strcmp (), utilice la primera char en su cadena para dividir sus datos en 256 clases, luego ordene cada clase en la próxima cadena disponible hasta que todo esté terminado.

Este método utiliza completamente todos los núcleos disponibles hasta que se resuelva el problema, y ​​creo que es fácil de implementar. No obstante, todavía no lo he implementado, por lo que aún puede haber problemas que aún tengo que encontrar. Claramente no puede funcionar para géneros de coma flotante, y sería ineficiente para s grandes. Su rendimiento también dependería en gran medida de la entropía del entero / char usado para definir las clases.

Esto puede ser lo que sugirió Fabian Steeg en pocas palabras, pero estoy explicitando que, en algunas circunstancias, puede crear ordenaciones múltiples más pequeñas de un tipo más amplio.

Answer 4

Java 8 proporciona java.util.Arrays.parallelSort , que ordena las matrices en paralelo utilizando el marco fork-join. La documentación proporciona algunos detalles sobre la implementación actual (pero estas son notas no normativas):

El algoritmo de clasificación es una fusión de clasificación paralela que divide la matriz en sub-arreglos que son ordenados y luego fusionados. Cuando la longitud del subarreglo alcanza una granularidad mínima, la matriz secundaria se ordena utilizando el método Arrays.sort apropiado. Si la longitud de la matriz especificada es menor que la granularidad mínima, entonces se ordena utilizando el método Arrays.sort apropiado. El algoritmo requiere un espacio de trabajo no mayor que el tamaño de la matriz original. El grupo común ForkJoin se usa para ejecutar tareas paralelas.

No parece haber un método de ordenación paralela correspondiente para las listas (aunque las listas de toArray deberían jugar bien con la ordenación), por lo que deberá utilizar toArray , ordenar esa matriz y almacenar el resultado nuevamente en la lista. (He hecho una pregunta sobre esto here ).

Answer 5

Lo siento, pero lo que estás pidiendo no es posible. Creo que alguien más mencionó que la ordenación está ligada a IO y probablemente sean correctas. El código de IBM de Doug Lea es una buena pieza de trabajo, pero creo que está destinado principalmente como un ejemplo sobre cómo escribir código. Si observas en su artículo que nunca publicó los puntos de referencia para él y en su lugar publicó puntos de referencia para otros códigos de trabajo, como el cálculo de promedios y la búsqueda del mínimo máximo en paralelo. Aquí está lo que son los puntos de referencia si utiliza una Clasificación de fusión genérica, Clasificación rápida, Clasificación de fusión de Dougs usando un Fondo de unión de horquilla, y uno que escribí utilizando un Grupo de horquilla de unión de clasificación rápida. Verás que Merge Sort es lo mejor para una N de 100 o menos. Quick Sort para 1000 a 10000 y Quick Sort usando un Fork de Join Pool supera al resto si tiene 100000 o más. Estas pruebas fueron de matrices de números aleatorios que se ejecutan 30 veces para crear un promedio para cada punto de datos y se ejecutaban en un núcleo cuádruple con aproximadamente 2 gigas de memoria RAM. Y a continuación tengo el código para la clasificación rápida. Esto muestra principalmente que, a menos que intente ordenar una matriz muy grande, debe evitar el algoritmo de clasificación de códigos, ya que los paralelos funcionan muy lentamente en N''s pequeñas.

Merge Sort
10  7.51E-06
100 1.34E-04
1000    0.003286269
10000   0.023988694
100000  0.022994328
1000000 0.329776132


Quick Sort
5.13E-05
1.60E-04
7.20E-04
9.61E-04
0.01949271
0.32528383


Merge TP
1.87E-04
6.41E-04
0.003704411
0.014830678
0.019474009
0.19581768

Quick TP
2.28E-04
4.40E-04
0.002716065
0.003115251
0.014046681
0.157845389

import jsr166y.ForkJoinPool;
import jsr166y.RecursiveAction;

//  derived from
//  http://www.cs.princeton.edu/introcs/42sort/QuickSort.java.html
//  Copyright © 2007, Robert Sedgewick and Kevin Wayne.
//  Modified for Join Fork by me hastily. 
public class QuickSort {

    Comparable array[];
    static int limiter = 10000;

    public QuickSort(Comparable array[]) {
        this.array = array;
    }

    public void sort(ForkJoinPool pool) {
        RecursiveAction start = new Partition(0, array.length - 1);        
        pool.invoke(start);
    }

    class Partition extends RecursiveAction {

        int left;
        int right;

        Partition(int left, int right) {
            this.left = left;
            this.right = right;
        }

        public int size() {
            return right - left;
        }

        @SuppressWarnings("empty-statement")
        //void partitionTask(int left, int right) {
        protected void compute() {
            int i = left, j = right;
            Comparable tmp;
            Comparable pivot = array[(left + right) / 2];

            while (i <= j) {
                while (array[i].compareTo(pivot) < 0) {
                    i++;
                }
                while (array[j].compareTo(pivot) > 0) {
                    j--;
                }

                if (i <= j) {
                    tmp = array[i];
                    array[i] = array[j];
                    array[j] = tmp;
                    i++;
                    j--;
                }
            }


            Partition leftTask = null;
            Partition rightTask = null;

            if (left < i - 1) {
                leftTask = new Partition(left, i - 1);
            }
            if (i < right) {
                rightTask = new Partition(i, right);
            }

            if (size() > limiter) {
                if (leftTask != null && rightTask != null) {
                    invokeAll(leftTask, rightTask);
                } else if (leftTask != null) {
                    invokeAll(leftTask);
                } else if (rightTask != null) {
                    invokeAll(rightTask);
                }
            }else{
                if (leftTask != null) {
                    leftTask.compute();
                }
                if (rightTask != null) {
                    rightTask.compute();
                }
            }
        }
    }
}

Answer 6

Probablemente haya considerado esto, pero podría ayudar a ver el problema concreto desde un nivel superior, por ejemplo, si no ordena solo una matriz o lista, sería mucho más fácil ordenar las colecciones individuales al mismo tiempo utilizando el algoritmo tradicional en lugar de tratando de ordenar al mismo tiempo una sola colección.

Answer 7

intentar darle una bifurcación / unir el marco por Doug Lea :

public class MergeSort extends RecursiveAction {
    final int[] numbers;
    final int startPos, endPos;
    final int[] result;

    private void merge(MergeSort left, MergeSort right) {
        int i=0, leftPos=0, rightPos=0, leftSize = left.size(), rightSize = right.size();
        while (leftPos < leftSize && rightPos < rightSize)
            result[i++] = (left.result[leftPos] <= right.result[rightPos])
                ? left.result[leftPos++]
                : right.result[rightPos++];
        while (leftPos < leftSize)
            result[i++] = left.result[leftPos++];
        while (rightPos < rightSize)
        result[i++] = right.result[rightPos++];
    }

    public int size() {
        return endPos-startPos;
    }

    protected void compute() {
        if (size() < SEQUENTIAL_THRESHOLD) {
            System.arraycopy(numbers, startPos, result, 0, size());
            Arrays.sort(result, 0, size());
        } else {
            int midpoint = size() / 2;
            MergeSort left = new MergeSort(numbers, startPos, startPos+midpoint);
            MergeSort right = new MergeSort(numbers, startPos+midpoint, endPos);
            coInvoke(left, right);
            merge(left, right);
        }
    }
}

(fuente: http://www.ibm.com/developerworks/java/library/j-jtp03048.html?S_TACT=105AGX01&S_CMP=LP )