Đếm một IOrderedEnumerable mà không tốn nhiều nó

Question

Những gì tôi muốn làm, phiên bản ngắn:

var source = new[]{2,4,6,1,9}.OrderBy(x=>x); 
int count = source.Count; // <-- get the number of elements without performing the sort 

---

dài phiên bản:

Để xác định số phần tử trong một IEnumerable, nó là cần thiết để lặp qua tất cả các phần tử. Đây có thể là một hoạt động rất tốn kém.

Nếu IEnumerable có thể được truyền tới ICollection, khi đó số lượng có thể được xác định nhanh chóng mà không cần lặp lại. Phương thức LINQ Count() thực hiện điều này một cách tự động.

Chức năng myEnumerable.OrderBy() trả về một IOrderedEnumerable. An IOrderedEnumerable rõ ràng không thể được truyền tới ICollection, vì vậy, hãy gọi Đếm() sẽ tiêu thụ toàn bộ.

Nhưng việc sắp xếp không thay đổi số lượng thành phần và IOrderedEnumerable phải giữ nguyên tham chiếu đến nguồn của nó. Vì vậy, nếu nguồn đó là ICollection, bạn có thể xác định số lượng từ IOrderedEnumerable mà không cần tiêu thụ.

Mục tiêu của tôi là có phương thức thư viện, cần có IEnumerable với các phần tử n và sau đó lấy phần tử ở vị trí n/2;

Tôi muốn tránh lặp lại trên IEnumerable hai lần chỉ để nhận số đếm, nhưng tôi cũng muốn tránh tạo bản sao không cần thiết nếu có thể.

---

Đây là một bộ xương của hàm Tôi muốn tạo

public void DoSomething(IEnumerable<T> source) 
{ 
    int count; // What we do with the source depends on its length 

    if (source is ICollection) 
    { 
     count = source.Count(); // Great, we can use ICollection.Count 
    } 
    else if (source is IOrderedEnumerable) 
    { 
     // TODO: Find out whether this is based on an ICollection, 
     // TODO: then determine the count of that ICollection 
    } 
    else 
    { 
     // Iterating over the source may be expensive, 
     // to avoid iterating twice, make a copy of the source 
     source = source.ToList(); 
     count = source.Count(); 
    } 

    // do some stuff 

} 

Answer 1

Hãy nghĩ gì mã này thực sự trông như:

var source = new[]{ 2, 4, 6, 1, 9 }.OrderBy(x => x); 
int count = source.Count(); 

Nó là giống như

int count = Enumerable.Count(Enumerable.OrderBy(new[]{ 2, 4, 6, 1, 9 }, x => x)); 

Kết quả Enumerable.OrderBy(new[]{ 2, 4, 6, 1, 9 }, x => x) được thông qua vào Count mở rộng. Bạn không thể tránh thực hiện OrderBy. Và do đó nó không phải là nhà điều hành trực tuyến, nó tiêu thụ tất cả các nguồn trước khi trả lại một cái gì đó, mà sẽ được chuyển đến Count.

Vì vậy, cách duy nhất để tránh lặp qua tất cả bộ sưu tập, là tránh OrderBy - đếm các mục trước khi sắp xếp.

---

UPDATE: Bạn có thể gọi phương thức tiện ích này trên bất kỳ OrderedEnumerable - nó sẽ sử dụng phản ánh để có được source lĩnh vực OrderedEnumerable<T> nắm giữ chuỗi nguồn. Sau đó kiểm tra nếu trình tự này là bộ sưu tập, và sử dụng Count mà không thực hiện đặt hàng:

public static class Extensions 
{ 
    public static int Count<T>(this IOrderedEnumerable<T> ordered) 
    { 
     // you can check if ordered is of type OrderedEnumerable<T> 
     Type type = ordered.GetType(); 
     var flags = BindingFlags.NonPublic | BindingFlags.Instance; 
     var field = type.GetField("source", flags); 
     var source = field.GetValue(ordered); 
     if (source is ICollection<T>) 
      return ((ICollection<T>)source).Count; 

     return ordered.Count(); 
    } 
} 

Cách sử dụng:

var source = new[]{ 2, 4, 6, 1, 9 }.OrderBy(x => x); 
int count = source.Count(); 

Answer 2

Nếu bạn đang tìm kiếm để tạo ra một giải pháp performant tôi muốn xem xét việc tạo quá tải mà phải mất một trong hai bộ sưu tập hoặc một IOrderedEnumerable vv .. tất cả những gì "là" và "như" typechecking và đúc không thể tốt cho loại điều bạn đang tạo ra.

Bạn đang phát minh lại bánh xe. Hàm "Count()" của linq thực hiện khá nhiều như bạn muốn.

Ngoài ra, hãy thêm từ khóa này và biến nó thành một phương thức tiện ích tiện lợi, để làm hài lòng bản thân và người khác bằng cách sử dụng mã.

DoSomething(this Collection source); 
DoSomething<T>(this List<T> source); 
DoSomething<T>(this IOrderedEnumerable<T> source); 

v.v ...

Answer 3

Một cách khác là để thực hiện một lớp mà thực hiện IOrderedEnumerable<T>. Sau đó, bạn có thể triển khai các thành viên lớp sẽ ngắn mạch các phương thức mở rộng Linq thông thường, và cung cấp một phương thức đếm nhìn vào liệt kê ban đầu.

public class MyOrderedEnumerable<T> : IOrderedEnumerable<T> 
{ 
    private IEnumerable<T> Original; 
    private IOrderedEnumerable<T> Sorted; 

    public MyOrderedEnumerable(IEnumerable<T> orig) 
    { 
      Original = orig; 
      Sorted = null; 
    } 

    private void ApplyOrder<TKey>(Func<T, TKey> keySelector, IComparer<TKey> comparer, bool descending) 
    { 
      var before = Sorted != null ? Sorted : Original; 
      if (descending) 
        Sorted = before.OrderByDescending(keySelector, comparer); 
      else 
        Sorted = before.OrderBy(keySelector, comparer); 
    } 

    #region Interface Implementations 

    public IEnumerator<T> GetEnumerator() 
    { 
      return Sorted != null ? Sorted.GetEnumerator() : Original.GetEnumerator(); 
    } 

    IEnumerator IEnumerable.GetEnumerator() 
    { 
      return GetEnumerator(); 
    } 

    public IOrderedEnumerable<T> CreateOrderedEnumerable<TKey>(
      Func<T, TKey> keySelector, 
      IComparer<TKey> comparer, 
      bool descending) 
    { 
      var newSorted = new MyOrderedEnumerable<T>(Original); 
      newSorted.ApplyOrder(keySelector, comparer, descending); 
      return newSorted; 
    } 

    #endregion Interface Implementations 


    //Ensure that OrderBy returns the right type. 
    //There are other variants of OrderBy extension methods you'll have to short-circuit 
    public MyOrderedEnumerable<T> OrderBy<TKey>(Func<T, TKey> keySelector) 
    { 
      Console.WriteLine("Ordering"); 
      var newSorted = new MyOrderedEnumerable<T>(Original); 
      newSorted.Sorted = (Sorted != null ? Sorted : Original).OrderBy(keySelector); 
      return newSorted; 
    } 

    public int Count() 
    { 
      Console.WriteLine("Fast counting.."); 
      var collection = Original as ICollection; 
      return collection == null ? Original.Count() : collection.Count; 
    } 

    public static void Test() 
    { 
      var nums = new MyOrderedEnumerable<int>(Enumerable.Range(0,10).ToList()); 
      var nums2 = nums.OrderBy(x => -x); 
      var z = nums.Count() + nums2.Count(); 
    } 
}