Java の分割統治のアイデアである ForkJoin を適用する方法

分割統治アルゴリズム

フォーク結合モードは、分割統治の考え方に基づく並列計算モードの 1 つです。このモードでは、大きなタスクを複数の小さなサブタスクに分割し、これらのサブタスクを並行して実行し、最後にそれらの結果をマージして最終結果を取得します。このプロセスでは、特定のしきい値に達するまで、各サブタスクの実行をさらに小さなサブタスクに分解することができ、しきい値に達するとタスクが連続して実行されます。この再帰的な分割統治の考え方により、フォーク結合モードでコンピュータのマルチコア処理能力を効果的に利用できるようになり、プログラムのパフォーマンスと効率が向上します。

マージ ソート

マージ ソートは、分割統治の考え方に基づいた並べ替えアルゴリズムです。中心となるアイデアは、配列を 2 つのサブ配列に分割し、それらを別々に並べ替えてからマージすることです。具体的な実装プロセスは次のとおりです。

• 分解: 配列を 2 つの部分配列に分割し、それぞれを並べ替えます。このステップは再帰を使用して実行できます。

• Merge: ソートされた 2 つのサブ配列を順序付き配列にマージします。

• 再帰: 各部分配列の長さが 1 になるまで、2 つの部分配列を再帰的に分解して並べ替えます。

時間計算量は 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];
        }
    }
}

クイック ソート

クイック ソートは、分割統治のアイデアに基づいたソート アルゴリズムです。再帰的手法を使用して、大きな配列をソートします。複数のサブ配列に分解され、個別にソートされてからマージされます。基本的な考え方は、ベンチマーク要素を選択し、左側の要素より小さい値、右側の要素より大きい値を配列に配置し、左右を再帰的に並べ替えることです。サブ配列。具体的な手順は次のとおりです。

• 参照要素 (通常は配列の最初の要素) を選択します。

• 配列の左側の要素より小さい値、右側の要素より大きい値を入れます。

• 左右の部分配列を再帰的にすばやく並べ替えます。

• ソートされた左右の部分配列をマージします。

クイック ソートの時間計算量は O(nlogn) です。これはインプレース ソート アルゴリズムであり、追加の記憶域スペースを必要としないため、スペース計算量は O(1) です。クイック ソートの最悪の時間計算量は O(n^2) ですが、実際のアプリケーションでは、クイック ソートの平均時間計算量と最良の時間計算量は両方とも O(nlogn) であるため、非常に効率的な方法です。

##

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

Fork/Join フレームワークの主なコンポーネントは、ForkJoinPool と ForkJoinTask です。 ForkJoinPool は、ForkJoin タスクの実行を管理するスレッド プールです。 ForkJoinTask は、より小さな部分に分割できるタスクを表すために使用される抽象クラスです。

ForkJoinPool

ForkJoinPool は、Fork/Join フレームワークのスレッド プール クラスで、Fork/Join タスクのスレッドを管理するために使用されます。 ForkJoinPool クラスには、submit()、invoke()、shutdown()、awaitTermination() などのいくつかの重要なメソッドが含まれており、これらはタスクの送信、タスクの実行、スレッド プールのクローズ、およびタスクの実行結果の待機に使用されます。タスク。 ForkJoinPool クラスには、スレッド プールのサイズ、ワーカー スレッドの優先順位、タスク キューの容量など、特定のアプリケーション シナリオに従って設定できるいくつかのパラメーターも含まれています。

Constructor

ForkJoinPool には 4 つのコア パラメータがあり、並列スレッド プールの数、ワーカー スレッドの作成、例外処理、およびモードの指定を制御するために使用されます。

• int 並列処理: 並列処理レベルを指定します。 ForkJoinPool は、この設定に基づいてワーカー スレッドの数を決定します。設定されていない場合、Runtime.getRuntime().availableProcessors() を使用して並列レベルを設定します。

• ForkJoinWorkerThreadFactory ファクトリ: スレッドの作成時に、ファクトリを通じて ForkJoinPool が作成されます。ここで実装する必要があるのは、ThreadFactory ではなく、ForkJoinWorkerThreadFactory であることに注意してください。ファクトリーを指定しない場合、デフォルトの DefaultForkJoinWorkerThreadFactory がスレッドの作成を担当します;

• UncaughtExceptionHandler ハンドラー: 例外ハンドラーを指定します。タスク中にエラーが発生した場合、それは次によって処理されます。セット ハンドラー。プロセッサ;

• boolean asyncMode: キューの動作モードを設定します。 asyncMode が true の場合、先入れ先出しキューが使用され、false の場合、後入れ先出しモードが使用されます。

ワークスチール方法

フォーク-ジョインモードでは、タスクは実行のためにスレッドプール内のワーカースレッドに割り当てられます。ワーカー スレッドは、割り当てられたタスクを完了すると、他のワーカー スレッドのタスク キューからタスクを盗んで実行できます。これをワーク スティーリングといいます。

使用

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

以上がJava の分割統治のアイデアである ForkJoin を適用する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。