So sánh giữa timsort và quicksort

Question

Tại sao tôi chủ yếu nghe về quicksort là thuật toán sắp xếp tổng thể nhanh nhất khi timsort (theo wikipedia) dường như hoạt động tốt hơn nhiều? Google dường như không có bất kỳ loại so sánh nào.

Answer 1

TimSort là kết hợp tối ưu hóa cao, nó ổn định và nhanh hơn so với sáp nhập cũ.

khi so sánh với quicksort, nó có hai ưu điểm:

1. Đó là khó tin nhanh cho chuỗi dữ liệu được sắp xếp gần (kể cả ngược sắp xếp dữ liệu);
2. Trường hợp xấu nhất vẫn là O (N * LOG (N)).

Thành thật mà nói, tôi không nghĩ rằng # 1 là một lợi thế, nhưng nó đã gây ấn tượng với tôi.

Dưới đây là lợi thế Sắp xếp nhanh của

1. Sắp xếp nhanh là rất rất đơn giản, thậm chí là một thực hiện điều chỉnh cao, chúng tôi có thể viết ra mã pseduo trong vòng 20 dòng;
2. QuickSort là nhanh nhất trong hầu hết các trường hợp;
3. Mức tiêu thụ bộ nhớ là LOG (N).

Hiện tại, Java 7 SDK triển khai timsort và một biến thể quicksort mới: tức là Dual Pivot QuickSort.

Nếu bạn cần sắp xếp ổn định, hãy thử timsort, nếu không hãy bắt đầu với quicksort.

Answer 2

Ít hoặc nhiều, nó phải làm với thực tế là Timsort là một thuật toán sắp xếp lai. Điều này có nghĩa là trong khi hai loại cơ bản mà nó sử dụng (sắp xếp Mergesort và Chèn) đều tồi tệ hơn Quicksort đối với nhiều loại dữ liệu, Timsort chỉ sử dụng chúng khi có lợi thế.

Ở mức hơi sâu hơn, như trạng thái Patrick87, quicksort là thuật toán O (n) tồi tệ nhất. Chọn trục xoay tốt không phải là hard, nhưng đảm bảo tốc độ nhanh O (n log n) đi kèm với chi phí phân loại thường chậm hơn.

Để biết thêm chi tiết về Timsort, hãy xem this answer và bài đăng trên blog được liên kết. Về cơ bản nó giả định rằng hầu hết dữ liệu đã được sắp xếp một phần và xây dựng "chạy" dữ liệu được sắp xếp cho phép hợp nhất hiệu quả bằng cách sử dụng mergesort.

Answer 3

Nói chung quicksort là thuật toán tốt nhất cho mảng nguyên thủy. Điều này là do bộ nhớ địa phương và bộ nhớ cache.

JDK7 sử dụng TimSort cho mảng Đối tượng. Mảng đối tượng chỉ giữ tham chiếu đối tượng. Bản thân đối tượng được lưu trữ trong Heap. Để so sánh đối tượng, chúng ta cần đọc đối tượng từ đống. Điều này giống như đọc từ một phần của heap cho một đối tượng, sau đó đọc ngẫu nhiên đối tượng từ một phần khác của heap. Sẽ có rất nhiều bộ nhớ cache bỏ lỡ. Tôi đoán lý do này khiến trí nhớ không còn quan trọng nữa. Đây có thể là lý do tại sao JDK chỉ sử dụng TimSort cho mảng Đối tượng thay vì mảng nguyên thủy.

Đây chỉ là phỏng đoán của tôi.

Answer 4

Dưới đây là số điểm chuẩn từ máy của tôi (CPU i7-6700, 3.4GHz, Ubuntu 16.04, gcc 5.4.0, các thông số: SIZE = 100000 và chạy = 3):

$ ./demo 
Running tests 
stdlib qsort time:     12246.33 us per iteration 
##quick sort time:     5822.00 us per iteration 
merge sort time:     8244.33 us per iteration 
...  
##tim sort time:     7695.33 us per iteration 
in-place merge sort time:   6788.00 us per iteration  
sqrt sort time:      7289.33 us per iteration  
... 
grail sort dyn buffer sort time: 7856.67 us per iteration 

Điểm chuẩn xuất phát từ dự án sort Swenson của, trong đó ông là thực hiện một số thuật toán sắp xếp trong C. lẽ, triển khai của mình là tốt, đủ để mang tính đại diện , nhưng tôi chưa điều tra chúng.

Vì vậy, bạn thực sự không thể biết được. Số điểm chuẩn chỉ có liên quan trong tối đa hai năm và sau đó bạn phải lặp lại chúng. Có thể, timsort đánh bại qsort waaay vào năm 2011 khi câu hỏi được hỏi, nhưng thời gian đã thay đổi. Hoặc qsort luôn là nhanh nhất, nhưng timsort đánh bại nó trên dữ liệu không ngẫu nhiên. Hoặc mã của Swenson không tốt và một lập trình viên tốt hơn sẽ biến thủy triều thành ưu tiên của timsort. Hoặc có lẽ tôi hút và không sử dụng quyền CFLAGS khi biên dịch mã. Hoặc ... Bạn nhận được điểm.