Cách tìm mục đầu tiên theo một thứ tự cụ thể bằng LINQ trong O (n)?

Question

Giả sử tôi có một danh sách các mục (ví dụ: Bài đăng) và tôi muốn tìm mục đầu tiên theo một số thứ tự không tầm thường (ví dụ: PublishDate và sau đó là CommentsCount là bộ ngắt kết nối). Cách tự nhiên để làm được điều này với LINQ là như thế này:

posts.OrderBy(post => post.PublishDate).ThenBy(post => post.CommentsCount).First() 

Tuy nhiên,-ưu vi trong tôi đang lo lắng rằng gọi OrderBy thực sự chi phí cho tôi O (n * LGN) để phân loại toàn bộ danh sách, khi tất cả Tôi thực sự cần là một hoạt động tìm kiếm tối thiểu O (n).

Vì vậy, LINQ có đủ thông minh để trả lại thứ gì đó từ OrderBy() biết cách tối ưu hóa các cuộc gọi First() tiếp theo không? Nếu không, cách tốt nhất để thực hiện việc này là gì? (Tôi luôn có thể viết thực hiện FindMinimumItem của riêng mình nhưng điều đó có vẻ như quá mức cần thiết).

Answer 1

Các phân loại là thông minh trong cách mà nó sẽ chỉ làm ThenBy vào nhóm đầu tiên từ OrderBy, nhưng OrderBy vẫn phải sắp xếp tất cả các mục trước khi nó có thể trả về nhóm đầu tiên.

Bạn có thể sử dụng phương pháp tổng hợp để có được những bài viết đầu tiên theo một so sánh tùy chỉnh: (. Giả sử rằng bạn đang sử dụng LINQ to Objects tất nhiên)

Post lowest = 
    posts.Aggregate((Post)null, 
    (x, y) => 
     x == null 
     || y.PublishDate < x.PublishDate 
     || (y.PublishDate == x.PublishDate && y.CommentsCount < x.CommentsCount) 
     ? y : x 
); 

Answer 2

Thường là max hoặc min (Tôi không biết nó được gọi như thế nào trong LinQ), được cung cấp một khóa cụ thể; phân loại và nhận được đầu tiên hoặc cuối cùng có vẻ quá mức cần thiết trong bất kỳ ngôn ngữ hoặc khuôn khổ nào.

Answer 3

Đây có phải là trong SQL hoặc LINQ to Objects không? Nếu sau này, bạn có thể muốn MinBy từ MoreLINQ; tuyên bố của bạn bằng văn bản sẽ thực sự sắp xếp và sau đó lấy mục đầu tiên.

Và có, đó là một sự xấu hổ rằng nó không bao gồm này (và những thứ tương tự như DistinctBy) ra khỏi hộp.

EDIT: Tôi thấy câu hỏi của bạn đã thay đổi; MoreLINQ không hỗ trợ so sánh hợp chất như vậy. Trong MiscUtil Tôi có mã để tạo hợp chất IComparer<T> - bạn có thể chuyển số đó vào MinBy bằng cách sử dụng chức năng nhận dạng làm công cụ chọn khóa. Cảm thấy tự do để thêm một yêu cầu tính năng cho một MinBy mà phải mất một nguồn và một IComparer<T> mà không có một selector chìa khóa :)