Có System.Linq.Enumerable.Reverse sao chép tất cả các phần tử trong nội bộ vào một mảng không?

Question

Một số năm trước, somebody complained about the implementation of Linq.Reverse() and Microsoft promised to fix that. Đây là năm 2008, do đó, câu hỏi là, Khung 4 có triển khai tối ưu Linq.Reverse() không thực hiện việc thu thập (tức là sao chép tất cả các phần tử vào mảng nội bộ) khi loại thu thập cho phép (ví dụ: IList<T>)?

Answer 1

Rõ ràng là không thể tối ưu hóa tất cả các trường hợp. Nếu một số đối tượng chỉ thực hiện IEnumerable<T> và không phải IList<T>, bạn phải lặp lại nó cho đến khi kết thúc để tìm phần tử cuối cùng. Vì vậy, tối ưu hóa sẽ chỉ dành cho các loại thực hiện IList<T> (như T[] hoặc List<T>).

Hiện tại, là nó thực sự được tối ưu hóa trong .Net 4.5 DP?Hãy cháy lên Reflector ILSpy:

public static IEnumerable<TSource> Reverse<TSource>(
    this IEnumerable<TSource> source) 
{ 
    if (source == null) 
    { 
     throw Error.ArgumentNull("source"); 
    } 
    return ReverseIterator<TSource>(source); 
} 

Được rồi, như thế nào ReverseIterator<TSource>() nhìn?

private static IEnumerable<TSource> ReverseIterator<TSource>(
    IEnumerable<TSource> source) 
{ 
    Buffer<TSource> buffer = new Buffer<TSource>(source); 
    for (int i = buffer.count - 1; i >= 0; i--) 
    { 
     yield return buffer.items[i]; 
    } 
    yield break; 
} 

Khối lặp đó là tạo Buffer<T> để thu thập và lặp lại thông qua đó. Chúng ta sắp sửa ở đó, Buffer<T> là gì?

[StructLayout(LayoutKind.Sequential)] 
internal struct Buffer<TElement> 
{ 
    internal TElement[] items; 
    internal int count; 
    internal Buffer(IEnumerable<TElement> source) 
    { 
     TElement[] array = null; 
     int length = 0; 
     ICollection<TElement> is2 = source as ICollection<TElement>; 
     if (is2 != null) 
     { 
      length = is2.Count; 
      if (length > 0) 
      { 
       array = new TElement[length]; 
       is2.CopyTo(array, 0); 
      } 
     } 
     else 
     { 
      foreach (TElement local in source) 
      { 
       if (array == null) 
       { 
        array = new TElement[4]; 
       } 
       else if (array.Length == length) 
       { 
        TElement[] destinationArray = new TElement[length * 2]; 
        Array.Copy(array, 0, destinationArray, 0, length); 
        array = destinationArray; 
       } 
       array[length] = local; 
       length++; 
      } 
     } 
     this.items = array; 
     this.count = length; 
    } 

    // one more member omitted 
} 

Chúng ta có gì ở đây? Chúng tôi sao chép nội dung vào một mảng. Trong mọi trường hợp. Tối ưu hóa duy nhất là nếu chúng ta biết Count (nghĩa là, bộ sưu tập thực hiện ICollection<T>), chúng tôi không phải phân bổ lại mảng.

Vì vậy, tối ưu hóa cho IList<T> là không phải trong .Net 4.5 DP. Nó tạo ra một bản sao của toàn bộ bộ sưu tập trong mọi trường hợp.

Nếu tôi đoán tại sao nó không được tối ưu hóa, sau khi đọc Jon Skeet's article on this issue, tôi nghĩ đó là vì tối ưu hóa đó có thể quan sát được. Nếu bạn thay đổi bộ sưu tập trong khi lặp lại, bạn sẽ thấy dữ liệu đã thay đổi với tối ưu hóa, nhưng dữ liệu cũ mà không có nó. Và tối ưu hóa thực sự thay đổi hành vi của một cái gì đó theo cách tinh tế là một điều xấu, vì khả năng tương thích ngược.

Answer 2

EDIT: Vâng, có vẻ như sự thay đổi này đã được thực hiện

Báo cáo lỗi bạn liên kết với vết lỗi như cố định, nhưng tôi muốn chắc chắn cho bản thân mình. Vì vậy, tôi đã viết chương trình nhỏ này:

static void Main(string[] args) 
{ 
    List<int> bigList = Enumerable.Range(0, 100000000).ToList(); 

    Console.WriteLine("List allocated"); 
    Console.ReadKey(); 

    foreach (int n in bigList.Reverse<int>()) 
    { 
     // This will never be true, but the loop ensures that we enumerate 
     // through the return value of Reverse() 
     if (n > 100000000) 
      Console.WriteLine("{0}", n); 
    } 
} 

Ý tưởng là chương trình phân bổ 400 MB dung lượng vào bigList, sau đó chờ đợi cho người dùng nhấn một phím, sau đó gọi Enumerable.Reverse(bigList) qua cú pháp phương pháp khuyến nông.

Tôi đã thử nghiệm chương trình này với bản dựng Gỡ lỗi trên máy tính Windows 7 x64. Việc sử dụng bộ nhớ của tôi trước khi bắt đầu chương trình là chính xác 2,00 GB, theo Task Manager. Sau đó, trước khi tôi nhấn phím, mức sử dụng bộ nhớ đạt 2,63 GB. Sau khi tôi nhấn phím, bộ nhớ sử dụng nhanh chóng tăng vọt lên 2,75 GB. Quan trọng hơn, mặc dù, nó không tăng đột biến 400 MB hoặc nhiều hơn, đó sẽ là trường hợp nếu Enumerable.Reverse() đang tạo một bản sao.

ORIGINAL POST

Đó là không thể đối với một đúng Enumerable.Reverse() thực hiện không sao chép vào một mảng hoặc cấu trúc dữ liệu khác trong một số tình huống.

Đơn khiếu nại bạn liên kết chỉ giao dịch với IList<T>. Tuy nhiên, trong trường hợp chung, tôi cho rằng Enumerable.Reverse()phải sao chép các phần tử vào một số bộ đệm trong.

Xem xét các phương pháp sau đây

private int x = 0; 

public IEnumerable<int> Foo() 
{ 
    for (int n = 0; n < 1000; n++) 
    { 
     yield return n; 
     x++; 
    } 
} 

Bây giờ chúng ta hãy nói rằng Enumerable.Reverse() không sao chép đầu vào IEnumerable<T> đến một bộ đệm trong trường hợp này. Sau đó, vòng lặp

foreach (int n in Foo().Reverse()) 
    Console.WriteLine("{0}", n); 

sẽ lặp tất cả các cách thức thông qua khối iterator để có được những n đầu tiên, tất cả các cách thức thông qua 999 yếu tố đầu tiên để có được những giây n, và vân vân. Nhưng điều này sẽ không có tác dụng tương tự trên x như lặp lại chuyển tiếp, bởi vì chúng tôi sẽ biến đổi x mỗi khi chúng tôi lặp lại gần như tất cả các cách thức thông qua giá trị trả lại của Foo(). Để ngăn chặn ngắt kết nối này giữa lặp lại chuyển tiếp và đảo ngược, phương thức Enumerable.Reverse()phải tạo bản sao của đầu vào IEnumerable<T>.