Scala Bộ sưu tập được sắp xếp, sortWith và SortBy Performance

Question

Scala bao gồm một số phương pháp trong các thư viện chuẩn để phân loại một danh sách, ví dụ để sắp xếp danh sách danh sách, người ta có thể sử dụng:

list.sorted 
list.sortWith(_<_) 
list.sortBy(x=>x) 

Trong khi những có thể là cách đơn giản nhất để sắp xếp danh sách, tôi thấy rằng đối với các danh sách lớn hơn, chúng có nhược điểm hiệu suất đáng kể.

Ví dụ: để sắp xếp một triệu số nguyên, sắp xếp mất 500ms trung bình, trong khi sortWith và sortBy mất khoảng 700ms. Điều này được so sánh với scala.util.Sorting.quickSort trong đó mất khoảng 120ms và java.util.Arrays.sort mất khoảng 100ms. Đối với các danh sách lớn hơn, sự khác biệt nhiều yếu tố này được quan sát thấy khi chúng tôi mở rộng hơn nữa. Mẫu được hiển thị trong biểu đồ sau.

Lý do cho sự chậm trễ này về hiệu suất là gì? Và tại sao các thuật toán/triển khai không hiệu quả hơn được sử dụng cho các phương pháp chuẩn?

Answer 1

Lưu ý cách các đường có cùng độ dốc, nhưng được bù trừ với nhau? Với quy mô lôgarít, chúng ta đang xem xét sự khác biệt về yếu tố không đổi. sorted và bạn bè trả chi phí chuyển đổi một số List thành số Array, sắp xếp (với số java.util.Arrays.sort, trên thực tế) và chuyển đổi lại thành List. scala.util.Sorting.quickSort và java.util.Arrays.sort hoạt động trên mảng trực tiếp. Các yếu tố log n trong quicksort của n log n hiệu suất phần lớn là không thích hợp, vì vậy với thời gian tuyến tính cần thiết để tạo ra các mảng và danh sách kết quả chúng tôi kết thúc với một sự khác biệt yếu tố không đổi. Hiệu suất năm lần tồi tệ hơn có thể trông khủng khiếp, nhưng hãy nhớ rằng List có một ô khuyết điểm cho mỗi phần tử, cho phép truy cập ngẫu nhiên một lượng lớn khi tạo Array và sau đó tạo mới List yêu cầu thời gian phân bổ bộ nhớ, và trong mọi khả năng, một chu kỳ thu gom rác hoặc hai.

Đối với danh sách nguyên thủy, thậm chí còn tồi tệ hơn. List là chung, vì vậy bất kỳ nguyên thủy phải được đóng hộp, mà thêm một lớp indirection. Và thật không may là Array được tạo cũng giữ giá trị được đóng hộp. Có hiệu quả, bạn kết thúc việc phân loại Array[java.lang.Integer] khi bạn thực sự muốn sắp xếp một Array[Int].

Để tóm tắt: các thuật toán sắp xếp giống hệt nhau, nhưng có lý do chính đáng khiến các mảng có thể thay đổi vượt trội hơn các danh sách được liên kết đơn lẻ không thay đổi.