Статьи

Введение в Fork / Join Framework

Январь 22, 2019

В предыдущих статьях о фреймворке java.util.concurrent я представил, что для меня является ядром пакета и что вы будете использовать чаще всего в реальных приложениях.

Если идти дальше с этой темой, то стоит знать о новой фреймворке fork / join, представленном в Java 7. Плюсы и минусы этой фреймворки по сравнению с использованием пулов потоков или обычной разработки потоков / выполнимых приложений были предметом многих дискуссий, но Я думаю, что это все еще хороший инструмент в вашем арсенале.

Я буду использовать более классический подход, чтобы показать вам базовую структуру структуры fork / join и использовать ее с помощью кода алгоритма Quicksort .

Моя цель — познакомить вас с инструментами, предоставляемыми структурой fork / join в Java 7, это не обсуждение лучшей реализации Quicksort. Если вы хотите вникнуть в лучшее из возможного Quicksort, я рекомендую вам прочитать этот замечательный пост об этом.

Среда fork / join предоставляет очень простую и интуитивно понятную структуру для реализации рекурсивных и разделяющих и побеждающих задач, которые могут быть решены одновременно. Вы начинаете с большой проблемы и разбиваете ее на более мелкие рабочие единицы, пока каждая рабочая единица не может быть решена напрямую.

Реализация вашего решения проблем должна быть подклассом ForkJoinTask , и вы, скорее всего, будете реализовывать подкласс его дочерних объектов RecursiveAction или RecursiveTask ; RecursiveAction представляет рекурсивное решение проблем, способное непосредственно решать достаточно малую проблему или разбивать ее на более мелкие рабочие блоки; RecursiveTask похож, но он также имеет возможность возвращать результат для каждого выполненного рабочего блока.

Для реализации нашей быстрой сортировки мы будем использовать стратегию на месте (мы хардкорные, верно?) И использовать общий список в качестве данных, чтобы он поддерживал любую Java Comparable. С этими предпосылками наша задача может быть закодирована как:

package com.ricardozuasti;
 
import java.util.List;
import java.util.concurrent.RecursiveAction;
 
public class QuickSort<T extends Comparable> extends RecursiveAction {
 
    private List<T> data;
    private int left;
    private int right;
 
    public QuickSort(List<T> data){
        this.data=data;
        this.left = 0;
        this.right = data.size() - 1;
    }
 
    public QuickSort(List<T> data, int left, int right){
        this.data = data;
        this.left = left;
        this.right = right;
    }
 
    @Override
    protected void compute() {
        if (left < right){
            int pivotIndex = left + ((right - left)/2);
 
            pivotIndex = partition(pivotIndex);
 
            invokeAll(new QuickSort(data, left, pivotIndex-1),
                      new QuickSort(data, pivotIndex+1, right));
        }
 
    }
 
    private int partition(int pivotIndex){
        T pivotValue = data.get(pivotIndex);
 
        swap(pivotIndex, right);
 
        int storeIndex = left;
        for (int i=left; i<right; i++){
            if (data.get(i).compareTo(pivotValue) < 0){
                swap(i, storeIndex);
                storeIndex++;
            }
        }
 
        swap(storeIndex, right);
 
        return storeIndex;
    }
 
    private void swap(int i, int j){
        if (i != j){
            T iValue = data.get(i);
 
            data.set(i, data.get(j));
            data.set(j, iValue);
        }
    }
}

Метод compute () — это метод, который будет вызывать инфраструктура fork / join для каждого рабочего модуля. Наш базовый шаг (небольшой рабочий блок) — ничего не делать (так как список размера 1 всегда сортируется). Наш рекурсивный шаг использует метод invokeAll () , который является ярлыком для fork () всех небольших рабочих модулей, а затем снова присоединяет их к ним () .

Вот и все! Нам больше ничего не нужно. Чтобы фактически использовать наш новый параллельный Quicksort, мы используем экземпляр ForkJoinPool :

package com.ricardozuasti;
 
import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.ForkJoinPool;
 
public class Concurrency3 {
    public static void main(String[] args) {
        final int SIZE = 10000;
 
        List<Integer> myList = new ArrayList<Integer>(SIZE);
 
        for (int i=0; i<SIZE; i++){
            int value = (int) (Math.random() * 100);
            myList.add(value);
        }
 
        QuickSort<Integer> quickSort = new QuickSort<Integer>(myList);
 
        ForkJoinPool pool = new ForkJoinPool();
        pool.invoke(quickSort);
    }
}

И снова метод invoke эквивалентен выполнению fork (), за которым следует join () , поэтому после возврата метода pool.invoke () наш список сортируется.

 

 

42
Share: