Quicksort multiproceso o mergesort

Question

¿Cómo puedo implementar un algoritmo quicksort o mergesort simultáneo para Java?

Hemos tenido problemas en un Mac de 16 (virtual) cores donde solo un núcleo (!) Funcionaba utilizando el algoritmo de ordenación predeterminado de Java y era, bueno, no era bueno ver que esa máquina muy fina fuera completamente infrautilizado 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 he encontrado en la web es un ejemplo de cómo no para escribir una clasificación rápida de múltiples subprocesos en Java, es de bucle de ocupados (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 mergesort en Java que provenga de una fuente acreditada?

Pongo énfasis en el hecho de que sé que la complejidad se mantiene en O (n log n), pero aún me gustaría mucho ver que todos estos núcleos comiencen 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 agradecería una aceleración x7 o x8 o incluso x16.

Answer 1

darle una oportunidad a fork/join framework by 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)

Answer 2

Probablemente tuvo en cuenta esto, pero podría ayudar a mirar el problema concreto de un nivel superior, por ejemplo, si no se 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 intentar ordenar al mismo tiempo una sola colección.

Answer 3

¿Por qué crees que una clasificación paralela 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 4

Disculpa, 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 5

He estado enfrentando el problema de clasificación de subprocesos múltiples el último par de días. Como se explica en on this caltech slide, lo mejor que puede hacer es simplemente multiprocesar cada paso de la división y conquistar enfoques sobre el número obvio de hilos (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.

Se me ocurrió una solución anoche que podría ser útil en mi propio trabajo, así que lo publicaré aquí.

Iff, el primer criterio de su función de clasificación se basa en un número entero s, ya sea un entero real o un carácter en una cadena, de modo que este entero o char define completamente el nivel más alto de su tipo, 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é listo .

Este método utiliza por completo todos los núcleos disponibles hasta que se solucione 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 haciendo explícito que puede crear varios tipos más pequeños de un tipo más grande en algunas circunstancias.

Answer 6

Acabo de codificar MergeSort 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);

Código de ensayo es:

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

pero tuvo que parar debido a los malos resultados.

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 alternativa al trabajo: http://blog.quibb.org/2010/03/jsr-166-the-java-forkjoin-framework/

Answer 7

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

El algoritmo de ordenación es una especie de combinación en paralelo que rompe la matriz en sub-matrices que son a su vez se separa y después se fusionaron.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 ser un método para ordenar paralelo correspondiente en las listas (aunque RandomAccess listas deberían jugar bien con la clasificación), por lo que tendrá que utilizar toArray, clasificar esa matriz, y almacenar el resultado en la lista. (He hecho una pregunta acerca de este here.)