Không phân loại bằng một công cụ so sánh "transitive" không có tính tương tác?

Question

Điều gì sẽ xảy ra nếu tôi cung cấp Comparator không chuyển đổi thành Collections.sort? Tôi có thể chạy vào vòng lặp vô hạn không?

Một thử nghiệm nhỏ mà tôi đã viết đã tạo ra kết quả đầu ra, nhưng tôi muốn đảm bảo điều này luôn đúng.

Vấn đề là trong một số trường hợp, bộ so sánh của tôi có thể tạo chu kỳ và trong trường hợp này tôi chỉ muốn đảm bảo nó sẽ không chạy vào vòng lặp vô hạn. Tôi không quan tâm đến kết quả thực tế.

Answer 1

Java docs nói rằng bạn phải đảm bảo rằng trình so sánh của bạn là chuyển đổi. Nếu bạn cung cấp một bộ so sánh không tuân theo những gì được yêu cầu, tất cả các cược sẽ bị tắt. Nó có thể làm việc cho một thực hiện nhất định nhưng có thể sụp đổ khủng khiếp (std::sort trong C++ không) trong một.

Tóm lại, bạn không nên dựa vào nó hoạt động ngay cả khi có một số ví dụ khác.

Answer 2

Collections.sort() được dựa trên mergesort.

tổng hợp lặp có tổng thể O (logn) lặp lại, vì kích thước mảng là ALWAYS chia, vì vậy sắp xếp() sẽ kết thúc, bất kể Comparator không phải là chuyển tiếp, vì vậy vòng lặp vô hạn sẽ không xảy ra.

Mặc dù, không có đảm bảo về thứ tự của Danh sách được tạo ra.

Answer 3

Hành vi của Collections.sort trong trường hợp này phụ thuộc vào việc triển khai thực hiện. Việc triển khai Java 6 SE sử dụng kết hợp Mergesort và Insertionsort, cả hai đều xác định với các trình so sánh không chuyển đổi nhưng trong Java 7 thuật toán Timsort được sử dụng và các triển khai khác có thể sử dụng Quicksort hoặc một thứ khác, vì vậy bạn không thể chắc chắn làm việc với tất cả các triển khai.

Answer 4

Trước hết, tôi khuyên bạn nên suy nghĩ về so sánh - là hoạt động từ bi thực sự quan hệ tương đương . Nếu bạn chấp nhận rằng nó không phải là và nó phải được - theo dõi so sánh các đối tượng trong một số biến địa phương. Biến cục bộ này có thể được so sánh với các đối tượng hoặc biến Thread Local. Biến này có thể là tập các cặp đối tượng được so sánh. Bên trong so sánh lời gọi phương thức kiểm tra xem cặp này đã được truy cập chưa - nếu đúng, quyết định phải làm gì. Nhưng lấy xe về Đặt các đối tượng được truy cập - nó thực sự nên chứa một cái gì đó như băm hoặc id đối tượng, bởi vì bạn có thể đi đến vô cùng theo cách khác. Và cũng lưu ý rằng việc lưu trữ cặp so sánh trong biến cục bộ là tiêu thụ bộ nhớ.

Answer 5

Vì Java 7 Collections.sort sử dụng TimSort. Sử dụng một so sánh không chuyển đổi để phân loại trong Java> = 7 sẽ ném ngoại lệ sau:

java.lang.IllegalArgumentException: Comparison method violates its general contract!