Đệ quy đa tuyến (Expenential Recursion)

Một bài toán kinh điển có thể áp dụng đệ quy đa tuyến (Expenential Recursion) là Merge Sort, một thuật toán sắp xếp nổi tiếng với thời gian chạy O(nlogn). Trong Merge Sort, chúng ta có thể chia mảng thành hai phần, sắp xếp từng phần riêng biệt bằng các luồng khác nhau, và sau đó hợp nhất chúng lại.

Dưới đây là cách triển khai Merge Sort với đệ quy đa tuyến trong C++, cùng với giải thích chi tiết.

Đệ quy đa tuyến cho Merge Sort:

#include <iostream>
#include <vector>
#include <thread>
#include <future>

// Hàm hợp nhất hai nửa của mảng đã được sắp xếp
void merge(std::vector<int>& arr, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;

    std::vector<int> L(n1);
    std::vector<int> R(n2);

    for (int i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (int i = 0; i < n2; i++)
        R[i] = arr[mid + 1 + i];

    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

// Hàm merge sort đệ quy
void mergeSort(std::vector<int>& arr, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;

        // Sử dụng std::async để sắp xếp song song hai nửa của mảng
        auto future_left = std::async(std::launch::async, mergeSort, std::ref(arr), left, mid);
        auto future_right = std::async(std::launch::async, mergeSort, std::ref(arr), mid + 1, right);

        // Đợi cả hai nửa được sắp xếp
        future_left.get();
        future_right.get();

        // Hợp nhất hai nửa đã được sắp xếp
        merge(arr, left, mid, right);
    }
}

int main() {
    std::vector<int> arr = {38, 27, 43, 3, 9, 82, 10};

    std::cout << "Unsorted array: ";
    for (int val : arr) std::cout << val << " ";
    std::cout << std::endl;

    mergeSort(arr, 0, arr.size() - 1);

    std::cout << "Sorted array: ";
    for (int val : arr) std::cout << val << " ";
    std::cout << std::endl;

    return 0;
}

Giải thích:

1. Thư viện <thread> và <future>:

   • Sử dụng <future> để tạo các tác vụ không đồng bộ và đồng bộ hóa kết quả.

2. Hàm merge:

   • Hàm merge kết hợp hai nửa đã được sắp xếp của mảng thành một mảng duy nhất đã được sắp xếp.
   • L và R là hai mảng tạm thời chứa các phần tử từ hai nửa của mảng chính.

3. Hàm mergeSort:

   • Hàm mergeSort chia mảng thành hai nửa, sau đó sắp xếp từng nửa một cách đệ quy.
   • std::async được sử dụng để thực hiện sắp xếp song song cho hai nửa của mảng.
   • future_left và future_right là các đối tượng std::future đại diện cho các tác vụ không đồng bộ sắp xếp hai nửa của mảng.
   • future_left.get() và future_right.get() đảm bảo rằng cả hai nửa của mảng đã được sắp xếp trước khi hợp nhất chúng lại.

4. Hàm main:

   • Tạo và in ra mảng ban đầu.
   • Gọi mergeSort để sắp xếp mảng.
   • In ra mảng đã được sắp xếp.

Hiệu quả:

• Tối ưu hóa đa tuyến: Sử dụng std::async để thực hiện sắp xếp song song hai nửa của mảng giúp tăng tốc độ sắp xếp, đặc biệt là trên các hệ thống đa nhân.
• Quản lý tài nguyên: Sử dụng std::future để đồng bộ hóa kết quả và đảm bảo rằng các tác vụ không đồng bộ hoàn thành trước khi tiếp tục.

Kết luận:

Sử dụng đệ quy đa tuyến để triển khai Merge Sort là một cách tiếp cận hiệu quả để tận dụng sức mạnh của các hệ thống đa nhân. Mặc dù quản lý luồng và đồng bộ hóa có thể phức tạp hơn so với việc sử dụng đệ quy tuần tự, nhưng với các công cụ như std::async và std::future trong C++, việc triển khai trở nên dễ dàng và hiệu quả hơn.