Multithread quicksort ou mergesort

essayer fork/join cadre de 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);
        }
    }
}

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

Java 8 fournit java.util.Arrays.parallelSort , qui trie les tableaux en parallèle en utilisant le cadre de fourche-join. La documentation fournit quelques détails sur la mise en œuvre actuelle (mais ce sont des notes non normatives):

l'algorithme de tri est une Tri-Fusion parallèle qui divise le tableau en sous-tableaux qui sont eux-mêmes triés puis fusionnés. Lorsque la longueur du sous-tableau atteint un minimum de granularité, le sous-tableau est trié utiliser les tableaux appropriés.méthode de tri. Si la longueur du tableau spécifié est inférieure à la granularité minimale, alors il est trié en utilisant les tableaux appropriés.méthode de tri. L'algorithme nécessite un espace de travail ne dépassant pas la taille du tableau original. Le pool commun ForkJoin est utilisé pour exécuter des tâches parallèles.

il ne semble pas y avoir de méthode de tri parallèle correspondante pour les listes (même si RandomAccess les listes devraient jouer avec le tri), donc vous devrez utiliser toArray , trier ce tableau, et stocker le résultat de nouveau dans la liste. (J'ai posé une question à propos de ce ici .)

Désolé, mais ce que vous demandez n'est pas possible. Je crois que quelqu'un d'autre a mentionné que le tri est lié à IO et qu'ils sont probablement corrects. Le code D'IBM par Doug Lea est une belle pièce de travail, mais je crois qu'il est destiné principalement comme un exemple sur la façon d'écrire du code. Si vous remarquez dans son article qu'il n'a jamais affiché les points de repère pour elle et plutôt affiché des points de repère pour d'autres code de travail tels que le calcul des moyennes et de trouver le min max en parallèle. Voici ce que l' les benchmarks sont si vous utilisez un tri générique de fusion, un tri rapide, un tri de fusion Dougs en utilisant un Pool de Join Fork, et un que j'ai écrit en utilisant un Pool de Join Fork rapide de tri. Vous verrez que la Fusion est la meilleure pour un N de 100 ou moins. Le tri rapide pour 1000 à 10000 et le tri rapide en utilisant un Pool de fourche de jointure bat le reste si vous avez 100000 et plus. Ces tests étaient des matrices de nombres aléatoires tournant 30 fois pour créer une moyenne pour chaque point de données et tournaient sur un noyau de quad avec environ 2 gigs de RAM. Et en dessous j'ai le code pour le Tri Rapide. Cela montre principalement qu'à moins que vous essayiez de trier un très grand tableau, vous devriez vous éloigner d'essayer d'améliorer votre algorithme de tri de codes puisque les parallèles tournent très lentement sur les petits N.

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

vient de coder la fusion ci-dessus et la performance était très faible.

le bloc de code fait référence à "coInvoke (gauche, droite);" mais il n'y avait aucune référence à cela et l'a remplacé par invokeAll (gauche, droite);

code D'essai:

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

, mais a dû arrêter en raison de mauvaises performances.

je vois que l'article ci-dessus a presque un an et peut-être que les choses ont changé maintenant.

j'ai trouvé le code dans l'article alternatif au travail: http://blog.quibb.org/2010/03/jsr-166-the-java-forkjoin-framework /

vous avez probablement considéré cela, mais il pourrait aider à examiner le problème concret d'un niveau plus élevé, par exemple si vous ne triez pas juste un tableau ou une liste il pourrait être beaucoup plus facile de trier des collections individuelles concurremment en utilisant l'algorithme traditionnel au lieu d'essayer de trier concurremment une collection unique.

j'ai été confronté au problème de tri multithread moi-même ces derniers jours. Comme expliqué sur cette diapositive caltech le mieux que vous pouvez faire en multithreading simplement chaque étape de la ligne de partage et de conquérir approches sur le nombre évident de fils (le nombre de divisions) est limitée. Je suppose que c'est parce que tandis que vous pouvez exécuter 64 divisions sur 64 threads en utilisant les 64 noyaux de votre machine, les 4 divisions ne peuvent être exécutées sur 4 threads, le 2 sur 2, et le 1 sur 1, etc. Donc pour de nombreux niveaux de la récursion votre machine est sous-utilisée.

une solution m'est venue hier soir qui pourrait être utile dans mon propre travail, donc je vais la poster ici.

Iff, le premier critère de votre fonction de tri est basé sur un entier de taille maximale s, que ce soit un entier réel ou un char dans une chaîne, de sorte que cet entier ou ce char définit complètement le niveau le plus élevé de votre sorte, alors je pense qu'il ya une solution très rapide (et facile). Il suffit d'utiliser ce nombre entier initial pour diviser votre problème de tri en s plus petits problèmes de tri, et de trier ceux qui utilisent le standard simple fileté tri algo de votre choix. La division en classes s peut se faire en un seul passage, je pense. Il n'y a pas de problème de fusion après avoir fait les tri indépendants, parce que vous savez déjà que tout dans la classe 1 tri avant la classe 2, et ainsi de suite.

Exemple : si vous souhaitez faire un tri basé sur strcmp(), puis utilisez le premier char dans votre chaîne de caractères pour décomposer vos données en 256 classes, puis trier chaque classe sur le prochain thread disponible jusqu'à ce qu'elles soient toutes terminées.

cette méthode utilise entièrement tous les noyaux disponibles jusqu'à ce que le problème soit résolu, et je pense qu'il est facile à mettre en œuvre. Je ne l'ai pas encore mis en œuvre, donc il peut y avoir des problèmes avec elle que je dois encore trouver. C'est clairement cant travail pour virgule flottante sortes, et serait inefficace pour s". Ses performances seraient également fortement dépendants l'entropie de l'entier/char utilisé pour définir les classes.

C'est peut-être ce que Fabian Steeg suggérait en moins de mots, mais je le rends explicite que vous pouvez créer plusieurs petites sortes à partir d'une plus grande sorte dans certaines circonstances.

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 e.g. 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[]>{
        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<a.length && j<b.length){
                    if(a[i] < b[j]){
                        result[k] = a[i];
                        i++;
                    } else{
                        result[k] = b[j];
                        j++;
                    }
                    k++;
                }

                while(i<a.length){
                    result[k] = a[i];
                    i++;
                    k++;
                }

                while(j<b.length){
                    result[k] = b[j];
                    j++;
                    k++;
                }

        return result;
    }
    }
}

Pourquoi pensez-vous qu'une sorte parallèle aiderait? Je pense que la plupart du tri est lié à l'entrée / sortie, pas au traitement. À moins que votre comparer fait beaucoup de calculs, une accélération est peu probable.