Bagaimana untuk menggunakan ForkJoin, idea bahagi dan takluk java

Algoritma Bahagi dan Takluk

Mod cantuman garpu ialah salah satu mod pengkomputeran selari berdasarkan idea bahagi dan takluk. Mod ini membahagikan tugasan besar kepada berbilang subtugas kecil, kemudian melaksanakan subtugasan ini secara selari, dan akhirnya menggabungkan keputusannya untuk mendapatkan hasil akhir. Dalam proses ini, pelaksanaan setiap subtugas boleh diuraikan lagi kepada subtugas yang lebih kecil sehingga ambang tertentu dicapai, pada masa itu tugasan akan dilaksanakan secara bersiri. Idea bahagi-dan-takluk rekursif ini membolehkan mod cantum garpu untuk menggunakan keupayaan pemprosesan berbilang teras komputer dengan berkesan, dengan itu meningkatkan prestasi dan kecekapan program.

Isih gabung

Isih gabung ialah algoritma isihan berdasarkan idea bahagi dan takluk. Idea teras adalah untuk membahagikan tatasusunan kepada dua sub-tatasusunan, menyusunnya secara berasingan dan kemudian menggabungkannya. Proses pelaksanaan khusus adalah seperti berikut:

• Penguraian: Bahagikan tatasusunan kepada dua sub-tatasusunan dan susun mereka masing-masing. Langkah ini boleh dicapai menggunakan rekursi.

• Gabung: Cantumkan dua subarray yang diisih ke dalam tatasusunan tertib.

• Rekursif: Uraikan dan susun dua subarray secara rekursif sehingga setiap subarray mempunyai panjang 1.

Kerumitan masa ialah 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];
        }
    }
}

Isih Pantas

Isih Pantas ialah algoritma pengisihan berdasarkan idea bahagi dan takluk Ia menggunakan kaedah rekursif untuk menyusun tatasusunan yang besar diuraikan kepada berbilang sub-tatasusunan, diisih secara berasingan dan kemudian digabungkan. Idea asasnya ialah memilih elemen penanda aras, meletakkan nilai dalam tatasusunan yang lebih kecil daripada elemen di sebelah kiri, nilai yang lebih besar daripada elemen di sebelah kanan, dan kemudian menyusun secara rekursif kiri dan kanan. sub-tatasusunan. Langkah-langkah khusus adalah seperti berikut:

• Pilih elemen rujukan (biasanya elemen pertama dalam tatasusunan).

• Letakkan nilai dalam tatasusunan yang lebih kecil daripada elemen di sebelah kiri, dan nilai yang lebih besar daripada elemen di sebelah kanan.

• Isih cepat secara rekursif masing-masing pada subtatasusunan kiri dan kanan.

• Gabungkan subtatasusunan yang diisih kiri dan kanan.

Kerumitan masa isihan pantas ialah O(nlogn) Ia adalah algoritma pengisihan di tempat dan tidak memerlukan ruang storan tambahan, jadi kerumitan ruang ialah O(1). Walaupun kerumitan masa terburuk bagi isihan pantas ialah O(n^2), dalam aplikasi praktikal, purata kerumitan masa dan kerumitan masa terbaik bagi isihan pantas ialah O(nlogn), jadi ia merupakan kaedah Isih

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

Komponen utama rangka kerja Fork/Join ialah ForkJoinPool dan ForkJoinTask. ForkJoinPool ialah kumpulan benang yang menguruskan pelaksanaan tugas ForkJoin. ForkJoinTask ialah kelas abstrak yang digunakan untuk mewakili tugasan yang boleh dibahagikan kepada bahagian yang lebih kecil.

ForkJoinPool

ForkJoinPool ialah kelas kumpulan benang dalam rangka kerja Fork/Join, yang digunakan untuk mengurus utas tugas Fork/Join. Kelas ForkJoinPool termasuk beberapa kaedah penting, seperti submit(), invoke(), shutdown(), awaitTermination(), dsb., yang digunakan untuk menyerahkan tugas, melaksanakan tugas, menutup kumpulan benang dan menunggu keputusan pelaksanaan tugasan. Kelas ForkJoinPool juga termasuk beberapa parameter, seperti saiz kumpulan benang, keutamaan benang pekerja, kapasiti baris gilir tugas, dll., yang boleh ditetapkan mengikut senario aplikasi tertentu.

Pembina

Terdapat empat parameter teras dalam ForkJoinPool, yang digunakan untuk mengawal bilangan kumpulan benang selari, penciptaan benang pekerja, pengendalian pengecualian dan spesifikasi mod, dsb.

• int paralelisme: Tentukan tahap paralelisme. ForkJoinPool akan menentukan bilangan rangkaian pekerja berdasarkan tetapan ini. Jika tidak ditetapkan, Runtime.getRuntime().availableProcessors() akan digunakan untuk menetapkan tahap selari; Ambil perhatian bahawa perkara yang perlu dilaksanakan di sini ialah ForkJoinWorkerThreadFactory, bukan ThreadFactory. Jika anda tidak menyatakan kilang, DefaultForkJoinWorkerThreadFactory lalai akan bertanggungjawab untuk penciptaan benang; pengendali set Pemproses;

• Boolean asyncMode: Tetapkan mod kerja baris gilir. Apabila asyncMode adalah benar, baris gilir pertama-masuk-dahulu akan digunakan dan apabila ia palsu, mod masuk-dahulu-keluar akan digunakan.

• Kaedah mencuri kerja

Dalam mod Fork-Join, tugasan diberikan kepada benang pekerja dalam kumpulan benang untuk dilaksanakan. Apabila benang pekerja menyelesaikan tugas yang diberikan, ia boleh mencuri (mencuri) tugas daripada baris gilir tugasan benang pekerja lain untuk dilaksanakan. Ini dipanggil mencuri kerja (Mencuri Kerja).

• Gunakan

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

Atas ialah kandungan terperinci Bagaimana untuk menggunakan ForkJoin, idea bahagi dan takluk java. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!