ARRAYS.PARALLELSORT – TÍNH NĂNG MỚI TRONG JAVA 8

1. Nhắc lại về Array.sort

API này dùng Merge sort hoặc Tim sort để sắp xếp đối tượng và mảng primitive.

    public static void sort(Object[] a) {
              if (LegacyMergeSort.userRequested) legacyMergeSort(a);
              else ComparableTimSort.sort(a);
       }

2. Array.paralelSort

Java 8 có API mới là Array.paralelSort sử dụng Fork/Join framework (đã có trong Java 7) để thực hiện sắp xếp với đa threads trong thread pool. Ý tưởng của việc sắp xếp paralelSort là chia mảng arrays ban đầu thành nhiều phần, mỗi phần do một Fork/Join thực hiện sắp xếp, và một Fork/Join khác merge các kết quả lại. Các bước thực hiện như sau:

• Chia array gốc thành 4 array nhỏ.
• Sắp xếp 2 mảng đầu rồi merge chúng lại làm 1.
• Sắp xếp 2 mảng tiếp theo rồi merge chúng lại làm 1.
• Các bước trên được lặp lại cho đến khi mỗi phần array con có kích thước không lớn hơn giá trị Threshold.

Threshold được tính toán như sau:

    private static final int getSplitThreshold (int n) {
        int p =  ForkJoinPool.getCommonPoolParallelism();

        int t = (p > 1) ? (1 + n / (p << 3)) : n;
        return t < MIN_ARRAY_SORT_GRAN ? MIN_ARRAY_SORT_GRAN : t;
    }

Kết quả là nếu sắp xếp mảng với kích thước lớn (khoảng 1000 phần tử) thì Array.paralelSort nhanh hơn Array.sort nhiều.

Một minh họa cho việc so sánh hiệu năng giữa Array.sort và Array.paralelSort.

Link tham khảo: http://blog.sanaulla.info/2013/04/08/arrays-sort-versus-arrays-parallelsort/