Tóm Tắt
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/
