Thuật toán phân loại nào được sử dụng bởi LINQ "OrderBy"?

Rõ ràng LINQ "OrderBy" ban đầu đã được chỉ định là không ổn định, nhưng vào thời điểm Orca nó được xác định là ổn định. Không phải tất cả các tài liệu đã được cập nhật cho phù hợp - cân nhắc những liên kết này:Thuật toán phân loại nào được sử dụng bởi LINQ "OrderBy"?

Nhưng nếu OrderBy LINQ là bây giờ "ổn định", sau đó nó có nghĩa là nó không được sử dụng một quicksort (mà vốn đã không ổn định) mặc dù một số tài liệu (ví dụ: sách của Troy) nói rằng đó là. Vì vậy, câu hỏi của tôi là: nếu không quicksort, thì thuật toán thực tế của LINQ orderBy đang sử dụng là gì?

Nguồn

2010-05-07 Brent Arias

Stictly, 'OrderBy' của Linq không được chỉ định để ổn định. 'Enumerable.OrderBy' được xác định là ổn định, các nhà cung cấp khác được tự do cung cấp lời hứa đó nhưng có thể không. Làm như vậy có thể là không thể hoặc rất tốn kém (xem xét tác động nó sẽ có trên parallelisation về p-linq ví dụ) hoặc tương đối rẻ, đó là một ảnh hưởng lớn về những gì các nhà cung cấp sẽ làm. –

Một bài đăng rất có liên quan [ở đây] (https://stackoverflow.com/q/148074/465053). – RBT

Đối với LINQ to Objects, đó là một quicksort ổn định được sử dụng. Đối với bất kỳ loại LINQ nào khác, nó còn lại để thực hiện bên dưới.

Nguồn

2010-05-07 22:57:55

Nếu tôi có một đối tượng được tham chiếu là chỉ 'IEnumerable ' thì Linq biết đó là Linq-to-Objects hay gì đó khác? – Dai

IEnumerable luôn là LINQ đối tượng (vs IQueryable là LINQ với bất kỳ thứ gì khác) – John

@Dai IEnumerable là một giao diện, vì vậy nó thực sự phụ thuộc vào loại có bộ sưu tập cơ bản (Tôi không đồng ý với @John). Ví dụ: Danh sách triển khai IEnumerable và bạn có thể có Danh sách được khai báo là IEnumerable . Nếu bạn thực hiện một đơn đặt hàng theo danh sách này, nhà cung cấp LINQ-to-objects được sử dụng. Mặt khác.DbSet cũng triển khai IEnumerable . Nếu bạn thực hiện một đơn hàng bằng DbSet này, ngay cả khi nó được khai báo là một IEnumerable, thì nhà cung cấp LINQ-to-sql sẽ được sử dụng. Nếu bạn muốn sử dụng linq-to-objects trên một dbset, bạn có thể làm dbset.AsEnumerable(). OrderBy (lambda) –

Tôi hiểu rằng OrderBy được dịch sang SQL thực hiện sắp xếp trên Cơ sở dữ liệu. Ít nhất là trong trường hợp của LINQ to SQL

Nguồn

2010-05-07 22:32:56

Có, nhưng điều đó chỉ đúng đối với LINQ to SQL và các nhà cung cấp cơ sở dữ liệu Linq khác. LINQ không chỉ là một ORM ... (LINQ to Objects, LINQ to XML ...) –

+1 Để xem xét một cái gì đó khác với LINQ to Objects –

Boot lên phản xạ, mở cửa cho System.Linq.EnumerableSorter tiết lộ rằng Linq2Objects sử dụng các loại nhanh chóng

Nguồn

2010-05-07 22:41:06 LorenVS

+1 để tìm kiếm nó –

+1 để tìm kiếm nó – helios456

+1 cho nhìn nó lên. Nhưng một thử nghiệm đơn giản cho thấy không có sự tăng trưởng n^2 trong thời gian tiêu thụ như là các yếu tố số lượng được sắp xếp ngược Danh sách tăng int, vì nó phải theo en.wikipedia.org/wiki/Quicksort Tôi đã thử 1k và 1M yếu tố trường hợp xấu nhất - thời gian mức tiêu thụ chỉ tăng khoảng 50 lần – EvAlex

Quicksort được sử dụng, nhưng lý do tại sao nó ổn định là vì các chỉ số của mỗi cặp yếu tố được so sánh nếu tất cả các phím kiểm tra bằng nhau.

Nói cách khác, bạn có thể thực hiện bất kỳ sự ổn định nhanh nào bằng cách bao gồm trong hàm so sánh so sánh các chỉ mục ban đầu của hai phần tử dưới dạng dự phòng.

Nguồn: http://referencesource.microsoft.com/#System.Core/System/Linq/Enumerable.cs,1395017e067e5a34

Nguồn

2015-05-07 04:49:20

cool. Tôi không biết điều đó – AaronHS

Thuật toán phân loại nào được sử dụng bởi LINQ "OrderBy"?

Trả lời

Các vấn đề liên quan