Sắp Xếp Mảng Song Song (Parallel Array Sort)

Parallel Array Sort được giới thiệu từ Java 8 trong lớp Arrays. Phương thức Arrays.parallelSort() cho phép sắp xếp mảng bằng cách sử dụng nhiều luồng xử lý song song (parallelism) để tăng hiệu suất, đặc biệt là trên các máy có nhiều CPU.

1. Phương thức parallelSort()

Phương thức này tương tự như phương thức Arrays.sort(), nhưng nó chia mảng thành nhiều phần nhỏ hơn và sắp xếp chúng song song sử dụng nhiều luồng.

• Cú pháp:

Arrays.parallelSort(array);

// Sắp xếp theo chỉ định
Arrays.parallelSort(array, fromIndex, toIndex);
// array: là mảng cần được sort
// fromIndex: vị trí bắt đầu
// toIndex: vị trí kết thúc

parallelSort() hỗ trợ các loại array sau: int[],
long[], double[] và T[] (với T là kiểu dữ liệu có thể so sánh, tức là T phải được implements từ Comparable)

• Ví dụ:

import java.util.Arrays;

public class App {
    public static void main(String[] args) {
        int[] numbers = {9, 3, 7, 5, 6, 8, 2, 4};
        
        // Sử dụng sắp xếp song song
        Arrays.parallelSort(numbers);
        
        // In mảng đã được sắp xếp
        System.out.println(Arrays.toString(numbers));
    }
}

import java.util.Arrays;

public class App {
    public static void main(String[] args) {
        int[] numbers = {9, 3, 7, 5, 6, 8, 2, 4};
        
        // Chỉ sắp xếp phần tử từ chỉ số 2 đến 5
        Arrays.parallelSort(numbers, 2, 6);
        
        // In mảng đã được sắp xếp
        System.out.println(Arrays.toString(numbers));
    }
}

2. Ưu điểm của parallelSort()

• Hiệu năng: parallelSort() đặc biệt hữu ích khi làm việc với các mảng lớn. Nó chia nhỏ công việc và thực hiện trên nhiều luồng do đó với các hệ thống nhiều core, hiệu năng có thể cải thiện đáng kể so với sắp xếp tuần tự.
• Tự động tối ưu: Java tự động quyết định số lượng luồng cần sử dụng dựa trên số core CPU.

3. Nhược điểm của parallelSort()

• Overhead: Nếu mảng nhỏ chi phí do việc quản lý luồng và chia nhỏ công việc có thể cao hơn lợi ích đạt được. Trong trường hợp này Arrays.sort() có thể nhanh hơn.
• Không phù hợp với mọi tình huống: Không phải lúc nào việc xử lý song song cũng mang lại lợi ích đặc biệt với các mảng nhỏ hoặc trong các môi trường đơn luồng (single-threaded).

4. So sánh Arrays.parallelSort với Arrays.sort()

• Arrays.sort() là phương thức sắp xếp tuần tự (sequential sort), nghĩa là nó thực hiện việc sắp xếp chỉ trên một luồng
• Arrays.parallelSort() chia công việc thành nhiều phần và sắp xếp song song trên nhiều luồng, do đó có thể nhanh hơn trong các hệ thống đa lõi với mảng lớn.

5. Câu hỏi phỏng vấn Parallel Array Sort

1. Parallel Sorting là gì?

Parallel Sorting là một tính năng mới từ Java 8 cho phép sắp xếp các mảng bằng cách sử dụng nhiều luồng song song để chia công việc và xử lý đồng thời tăng tốc độ sắp xếp trên các máy tính có nhiều core.

2. Sự khác biệt giữa Arrays.sort() và Arrays.parallelSort() là gì?

Arrays.sort() thực hiện sắp xếp tuần tự trên một luồng duy nhất còn Arrays.parallelSort() chia nhỏ mảng và thực hiện sắp xếp trên nhiều luồng song song. parallelSort() thường nhanh hơn với mảng lớn trên hệ thống đa core nhưng có thể chậm hơn với mảng nhỏ do chi phí quản lý luồng.

3. Khi nào nên sử dụng parallelSort() thay vì sort()?

parallelSort() hữu ích khi làm việc với mảng lớn trên các hệ thống có nhiều core CPU. Đối với các mảng nhỏ hoặc trên máy đơn lõi, sort() có thể hiệu quả hơn do không có chi phí quản lý luồng.

4. Phương thức parallelSort() chia nhỏ mảng như thế nào?

parallelSort() sử dụng thuật toán phân chia chia để trị (divide-and-conquer). Nó chia mảng thành các phần nhỏ hơn và sắp xếp từng phần một cách độc lập trên các luồng khác nhau sau đó kết hợp các phần đã sắp xếp để tạo thành kết quả cuối cùng.

5. Cấu trúc dữ liệu nào không phù hợp với Parallel Sort?

parallelSort() chỉ hoạt động trên các mảng (int[], long[], double[], và T[]). Đối với các cấu trúc dữ liệu như List, Set, hoặc Map chúng ta sẽ phải chuyển đổi chúng sang mảng trước khi sắp xếp hoặc sử dụng các phương thức sắp xếp tuần tự.

6. Chi phí (overhead) của việc sử dụng parallelSort() là gì?

Việc chia nhỏ công việc và quản lý các luồng song song đòi hỏi tài nguyên hệ thống như bộ nhớ và CPU. Với các mảng nhỏ thì chi phí này có thể cao hơn lợi ích từ việc xử lý song song dẫn đến thời gian thực thi lâu hơn so với việc sử dụng sort().

7. Java sử dụng các thuật toán nào trong parallelSort() và sort()?

Arrays.sort() cho mảng nguyên thủy sử dụng thuật toán Dual-Pivot Quicksort. Trong khi đó Arrays.parallelSort() sử dụng Merge Sort để thực hiện chia để trị và sắp xếp song song.

8. Điều gì xảy ra nếu một phần tử trong mảng không thể so sánh được khi sử dụng parallelSort()?

Nếu các phần tử của mảng không thể so sánh được một ngoại lệ ClassCastException sẽ được ném ra.

9. Làm thế nào để sắp xếp song song một phần của mảng?

Chúng ta có thể sử dụng phương thức Arrays.parallelSort(array, fromIndex, toIndex) để chỉ sắp xếp một phần của mảng từ fromIndex đến toIndex.

10. Nếu mảng có ít phần tử hơn số core CPU, parallelSort() có mang lại hiệu suất tốt hơn không?

Không, với mảng có ít phần tử hơn số core CPU, parallelSort() không mang lại hiệu suất tốt hơn vì chi phí quản lý luồng sẽ lớn hơn lợi ích của việc xử lý song song. Trong trường hợp này, sử dụng Arrays.sort() có thể tốt hơn.