Comment appliquer ForkJoin, l'idée Java diviser pour mieux régner

Algorithme Diviser et Conquérir

Le mode fork-join est l'un des modes de calcul parallèles basés sur l'idée de diviser pour mieux régner. Ce mode divise une grande tâche en plusieurs petites sous-tâches, puis exécute ces sous-tâches en parallèle et enfin combine leurs résultats pour obtenir le résultat final. Dans ce processus, l'exécution de chaque sous-tâche peut être décomposée en sous-tâches plus petites jusqu'à ce qu'un certain seuil soit atteint, moment auquel les tâches seront exécutées en série. Cette idée récursive de diviser pour régner permet au mode fork-join d'utiliser efficacement les capacités de traitement multicœur de l'ordinateur, améliorant ainsi les performances et l'efficacité du programme.

Tri par fusion

Le tri par fusion est un algorithme de tri basé sur l'idée de diviser pour mieux régner. L'idée principale est de diviser un tableau en deux sous-tableaux, de les trier séparément puis de les fusionner. Le processus de mise en œuvre spécifique est le suivant :

• Décomposition : divisez un tableau en deux sous-tableaux et triez-les respectivement. Cette étape peut être accomplie en utilisant la récursivité.

• Fusionner : fusionnez les deux sous-tableaux triés en un tableau ordonné.

• Récursif : décomposez et triez les deux sous-tableaux de manière récursive jusqu'à ce que la longueur de chaque sous-tableau soit de 1.

La complexité temporelle est O(nlogn).

public class Merge {
    public static void main(String[] args) {
        int[] arr = { 5, 2, 8, 4, 7, 1, 3, 6 };
        mergeSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }
    /**
     * 拆分
     * @param arr 数组
     * @param left 数组第一个元素
     * @param right 数组最后一个元素
     */
    public static void mergeSort(int[] arr,int left,int right){
        if (left < right) {
            int mid = (left + right) / 2;
            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);
            merge(arr, left, mid, right);
        }
    }
    /**
     * 合并
     * @param arr 数组
     * @param left 数组第一个元素
     * @param mid 数组分割的元素
     * @param right 数组最后一个元素
     */
    public static void merge(int[] arr,int left,int mid,int right){
        //创建临时数组，用于存放合并后的数组
        int[] temp = new int[right - left + 1];
        //左面数组的起始指针
        int i = left;
        //右面数组的起始指针
        int j = mid + 1;
        //临时数组的下标
        int k = 0;
        //数组左面和数组右面都还有值就去遍历比较赋值
        while (i <= mid && j <= right) {
            //数组左面的值小于或者等于数组右面的值就把左面的值赋值到临时数组中
            //并且把左面的指针和临时数组的指针+1
            //否则相反
            if (arr[i] <= arr[j]) {
                temp[k] = arr[i];
                k++;
                i++;
            } else {
                temp[k] = arr[j];
                k++;
                j++;
            }
        }
        //把剩余数组塞进去
        while (i <= mid) {
            temp[k] = arr[i];
            k++;
            i++;
        }
        while (j <= right) {
            temp[k] = arr[j];
            k++;
            j++;
        }
        //讲临时数组中的元素拷贝会回原数组中
        for (int p = 0; p < temp.length; p++) {
            arr[left + p] = temp[p];
        }
    }
}

Quick Sort

Quick Sort (Quick Sort) est un algorithme de tri basé sur l'idée de diviser pour mieux régner. Il utilise une méthode récursive pour décomposer un grand tableau en plusieurs sous-tableaux, puis les trier séparément. Ils fusionnent. L'idée de base est de sélectionner un élément de référence, de mettre dans le tableau les valeurs qui sont plus petites que l'élément de gauche, les valeurs qui sont plus grandes que l'élément de droite, puis de trier récursivement les valeurs de gauche et de droite. sous-tableaux. Les étapes spécifiques sont les suivantes :

• Sélectionnez un élément de référence (généralement le premier élément du tableau).

• Mettez dans le tableau les valeurs qui sont plus petites que l'élément de gauche et les valeurs qui sont plus grandes que l'élément de droite.

• Triez rapidement les sous-tableaux gauche et droit de manière récursive.

• Fusionnez les sous-tableaux triés à gauche et à droite.

La complexité temporelle du tri rapide est O(nlogn). Il s'agit d'un algorithme de tri sur place et ne nécessite pas d'espace de stockage supplémentaire, donc la complexité spatiale est O(1). Bien que la pire complexité temporelle du tri rapide soit O(n^2), dans les applications pratiques, la complexité temporelle moyenne et la meilleure complexité temporelle du tri rapide sont toutes deux O(nlogn), c'est donc une méthode de tri très efficace

.

public class QuickSort {
    public static void main(String[] args) {
        int[] arr = { 5, 2, 8, 4, 7, 1, 3, 6 };
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }
    public static void quickSort(int[] arr,int left,int right){
        if(left<right){
            int pivotIndex  = partition(arr, left, right);
            quickSort(arr,left,pivotIndex-1);
            quickSort(arr,pivotIndex+1,right);
        }
    }
    public static int partition(int[] arr,int left,int right){
        //取第一个元素为基准元素
        int pivot = arr[left];
        int i = left+1;
        int j = right;
        while (i<=j){
            //当前指针位置数小于基准元素就继续移动指针直到遇到大的
            while (i<=j && arr[i] < pivot){
                i++;
            }
            //当前指针位置数大于基准元素就继续移动指针直到遇到小的
            while (i<=j && arr[j] > pivot){
                j--;
            }
            if(i<j){
                //交换元素位置
                swap(arr,i,j);
                i++;
                j--;
            }
        }
        //跳出循环说明i和j相遇,j的值一定是大于基准元素,要和基准元素进行交换
        swap(arr,left,j);
        //返回基准元素位置
        return j;
    }
    public static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}

Fork/Join

Les principaux composants du framework Fork/Join sont ForkJoinPool et ForkJoinTask. ForkJoinPool est un pool de threads qui gère l'exécution des tâches ForkJoin. ForkJoinTask est une classe abstraite utilisée pour représenter des tâches qui peuvent être divisées en parties plus petites.

ForkJoinPool

ForkJoinPool est la classe de pool de threads dans le framework Fork/Join, qui est utilisée pour gérer les threads de la tâche Fork/Join. La classe ForkJoinPool comprend certaines méthodes importantes, telles que submit(), Ensure(), shutdown(), waitTermination(), etc., qui sont utilisées pour soumettre des tâches, exécuter des tâches, fermer le pool de threads et attendre les résultats d'exécution de tâches. La classe ForkJoinPool comprend également certains paramètres, tels que la taille du pool de threads, la priorité du thread de travail, la capacité de la file d'attente des tâches, etc., qui peuvent être définis en fonction de scénarios d'application spécifiques. Il existe quatre paramètres de base dans le

constructor

ForkJoinPool, qui sont utilisés pour contrôler le nombre de threads parallèles dans le pool de threads, la création de threads de travail, la gestion des exceptions et la spécification du mode, etc.

• int parallélisme : Spécifiez le niveau de parallélisme. ForkJoinPool déterminera le nombre de threads de travail en fonction de ce paramètre. S'il n'est pas défini, Runtime.getRuntime().availableProcessors() sera utilisé pour définir le niveau parallèle ;

• Fabrique ForkJoinWorkerThreadFactory : ForkJoinPool sera créé via l'usine lors de la création d'un thread. Notez que ce qui doit être implémenté ici est ForkJoinWorkerThreadFactory, et non ThreadFactory. Si vous ne spécifiez pas factory, le gestionnaire par défaut DefaultForkJoinWorkerThreadFactory sera responsable de la création du thread ;

• UncaughtExceptionHandler handler : spécifiez le gestionnaire d'exceptions lorsqu'une erreur se produit pendant la tâche, elle sera gérée par le gestionnaire set ; boolean asyncMode : définit le mode de fonctionnement de la file d'attente. Lorsque asyncMode est vrai, la file d'attente premier entré, premier sorti sera utilisée, et lorsqu'elle est fausse, le mode dernier entré, premier sorti sera utilisé.

• Work Stealing Method

En mode Fork-Join, les tâches sont assignées aux threads de travail dans un pool de threads pour exécution. Lorsqu'un thread de travail termine les tâches qui lui sont assignées, il peut voler (voler) des tâches dans les files d'attente de tâches d'autres threads de travail pour les exécuter. C'est ce qu'on appelle le vol de travail (Work Stealing).

Utilisez

public class SumTask extends RecursiveTask<Integer> {
    private static final int THRESHOLD = 1000;
    private int[] array;
    private int start;
    private int end;
    public SumTask(int[] array, int start, int end) {
        this.array = array;
        this.start = start;
        this.end = end;
    }
    @Override
    protected Integer compute() {
        if (end - start <= THRESHOLD) {
            int sum = 0;
            for (int i = start; i < end; i++) {
                sum += array[i];
            }
            return sum;
        } else {
            int mid = (start + end) / 2;
            SumTask leftTask = new SumTask(array, start, mid);
            SumTask rightTask = new SumTask(array, mid, end);
            leftTask.fork();
            rightTask.fork();
            int leftResult = leftTask.join();
            int rightResult = rightTask.join();
            return leftResult + rightResult;
        }
    }
    public static void main(String[] args) {
        int[] array = new int[10000];
        for (int i = 0; i < array.length; i++) {
            array[i] = i + 1;
        }
        ForkJoinPool forkJoinPool = new ForkJoinPool();
        SumTask task = new SumTask(array, 0, array.length);
        int result = forkJoinPool.invoke(task);
        System.out.println(result);
    }
}

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!