Tại sao việc triển khai sắp xếp của Java lại chuyển đổi danh sách sang mảng trước khi sắp xếp?

Question

Trong JDK 1.8, báo cáo kết quả đầu tiên của phương pháp java.util.List#sort(Comparator) như sau:

Object[] a = this.toArray(); 

Đó là tốn kém để sao chép danh sách vào một mảng, sắp xếp nó, và đặt lại tất cả các nút của danh sách với giá trị được sắp xếp từ mảng.

Có vẻ như không thể sao chép giá trị vào một mảng tạm thời khi sắp xếp một ArrayList. Tôi có đúng không? Nếu không, những gì đã hướng dẫn những người sáng tạo của phương pháp?

Answer 1

sort trong giao diện java.util.List chỉ là mặc định thực hiện sắp xếp danh sách.

ArrayList ghi đè mặc định này bằng phương pháp sắp xếp sắp xếp trực tiếp mảng nội bộ của nó.

Answer 2

Đối với ArrayList hoặc các Danh sách truy cập ngẫu nhiên khác, bạn có thể chính xác.

Tuy nhiên, Collections.sort hỗ trợ bất kỳ triển khai Danh sách nào. Ví dụ, đối với một LinkedList, nó sẽ rất mở rộng để hoán đổi các phần tử trong khi sắp xếp (vì việc tìm kiếm phần tử i'th mất thời gian tuyến tính).

Chuyển đổi danh sách thành mảng và đặt thành phần của danh sách ban đầu sau khi sắp xếp mảng sẽ thêm thành phần thời gian tuyến tính vào thuật toán, không thay đổi thời gian chạy tiệm cận của (O(nlog(n))).

Answer 3

Trong OpenJDK 1.8, java.util.ArrayList#sort(Comparator) không sao chép mảng nội bộ của nó; nó sắp xếp đúng chỗ, như bạn đề nghị.

Việc thực hiện java.util.List#sort() bạn đang chỉ trích có tài liệu hướng dẫn kèm theo sau đây:

Việc thực hiện mặc định có được một mảng chứa tất cả các yếu tố trong danh sách này, sắp xếp mảng, và lặp trên danh sách này đặt mỗi phần tử từ vị trí tương ứng trong mảng. (Điều này tránh sự n ² log (n) hiệu suất đó sẽ là kết quả của nỗ lực để sắp xếp một danh sách liên kết tại chỗ.)

Đó là, sao chép mảng và di chuyển xung quanh với truy cập ngẫu nhiên là hiệu quả hơn so với chi phí đi vòng quanh tuyến tính trong danh sách được liên kết. Các nỗ lực thực hiện phổ biến để giao dịch chi phí sao chép cho chi phí truy cập phần tử. Đối với các trường hợp như ArrayList trong trường hợp việc sao chép không cần thiết để có cùng quyền truy cập ngẫu nhiên vào các phần tử, thư viện bỏ qua bản sao bằng cách ghi đè phương thức.

Một so sánh thú vị: Nhìn vào C++ Library Standard std::sort() và std::list::sort() chức năng:

• std::sort() Yêu cầu thông số phân định một phạm vi với truy cập ngẫu nhiên.
• std::list::sort() Giả sử chỉ truy cập tuyến tính bằng cách duyệt qua các nút danh sách được liên kết.

Các generic std::sort() thuật toán hiệu quả hơn, nhưng thư viện ngăn cản gọi nó trên một std::list (mà là một danh sách liên kết, giống như Java java.util.LinkedList). Thư viện cung cấp một phương tiện kém hiệu quả hơn để sắp xếp một số std::list để thuận tiện. Không giống như thư viện Java, thư viện C++ không sao chép một std::list() vào một mảng để sử dụng thuật toán truy cập ngẫu nhiên std::sort().