Quicksort o mergesort multithread

Come posso implementare un quicksort concorrente o un algoritmo di mergesort per Java?

Abbiamo riscontrato problemi su un Mac (virtuale) a 16 picchi dove solo un core (!) Funzionava usando l’algoritmo di ordinamento Java predefinito ed era, beh, non bello vedere quella macchina molto fine essere completamente sottoutilizzata. Quindi abbiamo scritto il nostro (l’ho scritto io) e abbiamo effettivamente ottenuto una buona velocità (ho scritto un quicksread multithread e per via della sua natura di partizionamento è molto simile al parallelismo ma avrei potuto scrivere anche un mergesort) … Ma la mia implementazione solo scale fino a 4 thread, è un codice proprietario e preferirei usarne uno proveniente da una fonte affidabile invece di usare la mia ruota reinventata.

L’unico che ho trovato sul Web è un esempio di come non scrivere un quicksort multi-thread in Java, è occupato-looping (che è davvero terribile) usando un:

while (helpRequested) { } 

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

Quindi, oltre a perdere un thread senza motivo, è necessario assicurarsi di uccidere i perfs effettuando il ciclo di occupato in quel ciclo while (che è sconvolgente).

Da qui la mia domanda: sai di qualsiasi implementazione quicksort o multishare correttamente in Java che provenga da una fonte attendibile?

Metto l’accento sul fatto che so che la complessità rimane O (n log n), ma mi piacerebbe moltissimo vedere tutti questi core iniziare a funzionare invece che al minimo. Si noti che per altri compiti, su quello stesso 16 core virtuali del Mac, ho visto l’accelerazione fino a x7 parallelizzando il codice (e non sono affatto un esperto in concorrenza).

Quindi, anche se la complessità rimane O (n log n), apprezzerei molto un aumento di velocità x7 o x8 o addirittura x16.

dare una prova a fork / join quadro di 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); } } } 

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

Java 8 fornisce java.util.Arrays.parallelSort , che ordina gli array in parallelo usando il framework fork-join. La documentazione fornisce alcuni dettagli sull’attuale implementazione (ma si tratta di note non normative):

L’algoritmo di ordinamento è un’unione di ordinamento parallelo che interrompe l’array in matrici secondarie che vengono ordinate e quindi unite. Quando la lunghezza dell’array secondario raggiunge una granularità minima, la matrice secondaria viene ordinata utilizzando il metodo Arrays.sort appropriato. Se la lunghezza dell’array specificato è inferiore alla granularità minima, viene ordinata utilizzando il metodo Arrays.sort appropriato. L’algoritmo richiede uno spazio di lavoro non superiore alla dimensione dell’array originale. Il pool comune ForkJoin viene utilizzato per eseguire attività parallele.

Non sembra esserci un corrispondente metodo di ordinamento parallelo per gli elenchi (anche se gli elenchi di RandomAccess dovrebbero giocare con l’ordinamento), quindi sarà necessario utilizzare toArray , ordinare quell’array e archiviare il risultato nell’elenco. (Ho fatto una domanda su questo qui .)

Mi dispiace per questo, ma quello che chiedi non è ansible. Credo che qualcun altro abbia menzionato che lo smistamento è legato all’IO e probabilmente sono corretti. Il codice di IBM di Doug Lea è un bel lavoro, ma credo che sia inteso principalmente come esempio su come scrivere codice. Se si nota nel suo articolo non ha mai pubblicato i benchmark per esso e ha invece pubblicato benchmark per altri codici di lavoro come calcolare le medie e trovare il minimo massimo in parallelo. Ecco quali sono i benchmark se si utilizza un ordinamento di unione generico, un ordinamento rapido, un ordinamento di unione di dougs utilizzando un pool di fork join e uno che ho scritto utilizzando un pool di fork di join rapido. Vedrai che Merge Sort è il migliore per un N di 100 o meno. Ordinamento rapido da 1000 a 10000 e l’ordinamento rapido utilizzando un pool di forche di unione supera il resto se si dispone di 100000 e oltre. Questi test erano di array di numeri casuali in esecuzione 30 volte per creare una media per ogni punto di dati e funzionavano su un quad core con circa 2 giga di ram. E sotto ho il codice per l’ordinamento rapido. Questo dimostra principalmente che, a meno che non si stia tentando di ordinare un array molto grande, si dovrebbe evitare di provare a migliorare l’algoritmo di ordinamento dei codici poiché quelli paralleli funzionano molto lentamente sulle N piccole.

 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(); } } } } } 

Ho appena scritto MergeSort e le prestazioni sono state molto scarse.

Il blocco di codice si riferisce a “coInvoke (sinistra, destra);” ma non c’era alcun riferimento a questo e lo ha sostituito con invokeAll (sinistra, destra);

Il codice di prova è:

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

ma ha dovuto fermarlo a causa delle scarse prestazioni.

Vedo che l’articolo qui sopra ha quasi un anno e forse ora le cose sono cambiate.

Ho trovato il codice nell’articolo alternativo per funzionare: http://blog.quibb.org/2010/03/jsr-166-the-java-forkjoin-framework/

Probabilmente lo hai preso in considerazione, ma potrebbe essere utile esaminare il problema concreto da un livello superiore, ad esempio se non si ordina solo un array o un elenco potrebbe essere molto più semplice ordinare le singole raccolte contemporaneamente utilizzando l’algoritmo tradizionale anziché cercando di ordinare contemporaneamente una singola raccolta.

Ho affrontato il problema del sortilegio multithread negli ultimi due giorni. Come spiegato su questa slide caltech, il meglio che puoi fare semplicemente sovrapponendo ogni passo degli approcci di divisione e conquista sul numero ovvio di thread (il numero di divisioni) è limitato. Immagino che questo perché mentre puoi eseguire 64 divisioni su 64 thread usando tutti i 64 core della tua macchina, le 4 divisioni possono essere eseguite solo su 4 thread, 2 su 2 e 1 su 1, ecc. Quindi per molti livelli della ricorsione la tua macchina è sottoutilizzata.

La scorsa notte mi è stata presentata una soluzione che potrebbe essere utile nel mio lavoro, quindi la posterò qui.

Iff, il primo criterio della tua funzione di ordinamento si basa su un numero intero di dimensioni massime s, sia esso un intero effettivo o un carattere in una stringa, in modo tale che questo intero o carattere definisca completamente il livello più alto del tuo ordinamento, quindi penso che ci sia una soluzione molto veloce (e facile). Basta usare quel numero intero iniziale per dividere il tuo problema di ordinamento in s problemi di ordinamento più piccoli, e ordinare quelli che usano l’algoritmo standard di ordinamento a thread singolo di tua scelta. La divisione in classi s può essere fatta in un unico passaggio, penso. Non esiste un problema di unione dopo aver eseguito gli ordinamenti indipendenti, perché sai già che tutto nella class 1 ordina prima della class 2 e così via.

Esempio: se desideri eseguire un ordinamento basato su strcmp (), usa il primo carattere nella stringa per suddividere i tuoi dati in 256 classi, quindi ordina ogni class sul successivo thread disponibile fino a quando non sono completati.

Questo metodo utilizza completamente tutti i core disponibili fino a quando il problema non viene risolto e penso che sia facile da implementare. Non l’ho ancora implementato, quindi potrebbero esserci dei problemi che non ho ancora trovato. Evidentemente non può funzionare per specie in virgola mobile, e sarebbe inefficiente per grandi s. Le sue prestazioni dipenderebbero anche dall’entropia del numero intero / carattere utilizzato per definire le classi.

Questo potrebbe essere ciò che Fabian Steeg stava suggerendo in poche parole, ma sto rendendo esplicito che in alcune circostanze è ansible creare più tipi più piccoli da un tipo più grande.

 import java.util.Arrays; import java.util.concurrent.ForkJoinPool; import java.util.concurrent.RecursiveTask; public class IQ1 { public static void main(String[] args) { // Get number of available processors int numberOfProcessors = Runtime.getRuntime().availableProcessors(); System.out.println("Number of processors : " + numberOfProcessors); // Input data, it can be anything eg log records, file records etc long[][] input = new long[][]{ { 5, 8, 9, 14, 20 }, { 17, 56, 59, 80, 102 }, { 2, 4, 7, 11, 15 }, { 34, 37, 39, 45, 50 } }; /* A special thread pool designed to work with fork-and-join task splitting * The pool size is going to be based on number of cores available */ ForkJoinPool pool = new ForkJoinPool(numberOfProcessors); long[] result = pool.invoke(new Merger(input, 0, input.length)); System.out.println(Arrays.toString(result)); } /* Recursive task which returns the result * An instance of this will be used by the ForkJoinPool to start working on the problem * Each thread from the pool will call the compute and the problem size will reduce in each call */ static class Merger extends RecursiveTask{ long[][] input; int low; int high; Merger(long[][] input, int low, int high){ this.input = input; this.low = low; this.high = high; } @Override protected long[] compute() { long[] result = merge(); return result; } // Merge private long[] merge(){ long[] result = new long[input.length * input[0].length]; int i=0; int j=0; int k=0; if(high - low < 2){ return input[0]; } // base case if(high - low == 2){ long[] a = input[low]; long[] b = input[high-1]; result = mergeTwoSortedArrays(a, b); } else{ // divide the problem into smaller problems int mid = low + (high - low) / 2; Merger first = new Merger(input, low, mid); Merger second = new Merger(input, mid, high); first.fork(); long[] secondResult = second.compute(); long[] firstResult = first.join(); result = mergeTwoSortedArrays(firstResult, secondResult); } return result; } // method to merge two sorted arrays private long[] mergeTwoSortedArrays(long[] a, long[] b){ long[] result = new long[a.length + b.length]; int i=0; int j=0; int k=0; while(i 

Perché pensi che un tipo parallelo potrebbe aiutare? Penserei che la maggior parte dell’ordinamento sia legato / non associato, non elaborato. A meno che il tuo confronto non faccia molti calcoli, è improbabile un eccesso di velocità.