Timsort là một sự hợp nhất tự nhiên, ổn định, . Nó có siêu nhiên hiệu suất trên nhiều loại phần mảng trật tự (ít hơn lg (N!) so sánh cần thiết, và càng ít càng N-1), tuy nhiên càng nhanh càng chỉnh cao hybrid samplesort trước Python về mảng ngẫu nhiên .Có phải là mục đích chung theo thời gian hoặc Python cụ thể không?
Bạn đã xem timsort được sử dụng bên ngoài CPython chưa? Nó có ý nghĩa không?
Có, nó khá có ý nghĩa khi sử dụng timsort bên ngoài CPython, cụ thể hoặc Python nói chung.
Hiện tại có effort underway để thay thế "sắp xếp hợp nhất đã sửa đổi" của Java với dấu thời gian và kết quả ban đầu khá tích cực.
Java SE 7 sử dụng Timsort như thuật toán sắp xếp của nó ngay bây giờ. Xem http://www.docjar.com/docs/api/java/util/Collections.html#sort(List) –
Mô tả bạn đã liên kết trông hoàn toàn chung chung.
Có, nhưng bạn đã thấy timsort được sử dụng bên ngoài CPython chưa? – Constantin
Nó trông không quen thuộc lắm, nhưng sự hợp nhất "thông minh" khá phổ biến trong thế giới phần mềm rộng.
Cho dù điều đó có hợp lý hay không, điều đó phụ thuộc vào những gì bạn sắp xếp và chi phí so sánh tương đối so với phân bổ bộ nhớ. Một loại yêu cầu lên đến 2 * N byte bộ nhớ phụ sẽ không phải là một lựa chọn tốt trong môi trường hạn chế bộ nhớ.
Thuật toán khá chung chung, nhưng lợi ích khá cụ thể về Python. Không giống như hầu hết các thường trình sắp xếp, list.sort của Python (cái mà sử dụng timsort) quan tâm là tránh các so sánh không cần thiết, bởi vì so sánh chung là số lot đắt hơn các mục hoán đổi (luôn luôn là một tập hợp các bản sao con trỏ) hoặc thậm chí phân bổ một số bộ nhớ bổ sung (vì nó luôn luôn là một mảng con trỏ, và chi phí nhỏ hơn so với chi phí trung bình trong bất kỳ hoạt động Python nào.)
Nếu bạn có những hạn chế tương tự, thì nó có thể phù hợp. Tôi chưa thấy bất kỳ trường hợp nào khác mà so sánh thực sự đắt, mặc dù :-)
Nếu so sánh là tốn kém, thì thuật toán cụ thể cho dữ liệu thường sẽ hoạt động tốt hơn so với thuật toán dựa trên so sánh. –
Đó là một quan sát tốt, và thực sự có lẽ lý do chính bạn sẽ không thấy timsort hoặc bất cứ điều gì gần gũi với nó trong tự nhiên. –
Đã trả lời ngay bây giờ trên Wikipedia: timsort sẽ được sử dụng trong Java 7 đã sao chép từ Android.
Timsort cũng có trong Android ngay bây giờ: http://www.kiwidoc.com/java/l/x/android/android/5/p/java.util/c/TimSort
tại sao bạn yêu cầu? không có ngữ cảnh nhiều hơn, câu hỏi của bạn không thể trả lời được. – hop
Bạn có nhận thấy "Bạn đã xem timsort được sử dụng bên ngoài CPython chưa?" phần? – Constantin
tôi đã nhận thấy nó, và nó vẫn cho chúng ta không bối cảnh. bạn sẽ học được gì từ câu trả lời "không" đơn giản là câu trả lời? – hop