Hiệu suất của phương thức mở rộng Last() cho Danh sách <T> là gì?

Question

Tôi thực sự thích Last() và sẽ sử dụng nó mọi lúc cho List<T> s. Nhưng vì nó có vẻ được định nghĩa cho IEnumerable<T>, tôi đoán nó liệt kê các liệt kê đầu tiên - điều này nên là O (n) trái ngược với O (1) để lập chỉ mục trực tiếp phần tử cuối cùng của List<T>.

Phương thức mở rộng tiêu chuẩn (LINQ) có nhận thức được điều này không?

STL trong C++ nhận thức được điều này nhờ vào toàn bộ "cây thừa kế" cho trình lặp và không biết gì.

Answer 1

tôi chỉ sử dụng phản xạ nhìn vào mã cho cuối và nó sẽ kiểm tra xem nếu nó là một IList<T> đầu tiên và thực hiện các O thích hợp (1) gọi:

---

EDIT:

Theo lời khuyên của luật sư của tôi, tôi đã xóa đoạn mã khỏi phản xạ. Nếu bạn muốn xem mã cho chính mình, tôi đề nghị bạn nên lấy Reflector và tự mình làm (mà mọi người nên có) hoặc đơn giản là nhìn vào lịch sử sửa đổi của bài đăng này (vì tôi không thể làm gì được)

(Hoặc thực sự nhìn vào câu trả lời của Mark người rõ ràng không có đội ngũ pháp lý như nhau nứt bảo vệ anh ấy)

---

Vì vậy, bạn có overhead nhẹ của một diễn viên, nhưng không phải là chi phí rất lớn của các liệt kê.

Answer 2

Nó chứa tối ưu hóa cho bất kỳ thứ gì triển khai IList<T> trong trường hợp này, nó chỉ tìm kiếm mục ở độ dài -1.

Hãy ghi nhớ rằng đại đa số những thứ bạn sẽ sai đến nhân sẽ thực hiện IList<T>

List<int> 
int[] 

và vân vân ... tất cả thực hiện IList<T>

Đối với những người không thể nhìn vào mã để xác nhận, bạn có thể khẳng định nó bằng cách quan sát:

using System; 
using System.Collections.Generic; 
using System.Linq; 
using System.Text; 
using System.Diagnostics; 

namespace ConsoleApplication4 { 
    class Program { 

     static void Profile(string description, int iterations, Action func) { 

      // clean up 
      GC.Collect(); 
      GC.WaitForPendingFinalizers(); 
      GC.Collect(); 

      // warm up 
      func(); 

      var watch = Stopwatch.StartNew(); 
      for (int i = 0; i < iterations; i++) { 
       func(); 
      } 
      watch.Stop(); 
      Console.Write(description); 
      Console.WriteLine(" Time Elapsed {0} ms", watch.ElapsedMilliseconds); 
     } 

     static void Main(string[] args) { 
      int[] nums = Enumerable.Range(1, 1000000).ToArray(); 

      int a; 

      Profile("Raw performance", 100000,() => { a = nums[nums.Length - 1]; }); 
      Profile("With Last", 100000,() => { a = nums.Last(); }); 

      Console.ReadKey(); 
     } 


    } 
} 

Output:

0.123.

 
Raw performance Time Elapsed 1 ms 
With Last Time Elapsed 31 ms 

Vì vậy, nó chỉ chậm hơn 30 lần và duy trì hồ sơ hiệu suất đó với bất kỳ danh sách độ dài nào bạn có, không có gì trong sơ đồ lớn của sự vật.

Answer 3

Đối với List<T> là O (1), nhưng đối với các số khác có thể là O (N).

Answer 4

Bạn chỉ có thể sử dụng cuối với List<T> mà không lo lắng :)

Enumerable.Last cố gắng downCast sơ thẩm IEnumerable<T>-IList<T>. Nếu điều này là có thể, nó sẽ sử dụng thuộc tính indexer và Count.

Dưới đây là một phần của việc thực hiện như Reflector nhìn thấy nó:

IList<TSource> list = source as IList<TSource>; 
if (list != null) 
{ 
    int count = list.Count; 
    if (count > 0) 
    { 
     return list[count - 1]; 
    } 
} 

Answer 5

Câu trả lời ngắn:

O (1).

Giải thích:

Đó là điều hiển nhiên rằng cuối() cho Danh sách sử dụng Count() phương pháp khuyến nông.

Đếm() kiểm tra loại bộ sưu tập trong thời gian chạy và sử dụng Đếm nếu có.

Đếm thuộc tính cho danh sách có O (1) độ phức tạp như vậy là Phương thức mở rộng cuối cùng().