List <T> için Last() uzantı yönteminin performansı nedir?

Question

Last()'u gerçekten çok seviyorum ve List<T> s için her zaman kullanıyorum. Ancak, IEnumerable<T> için tanımlanmış gibi göründüğü için, önce numaralandırmayı numaralandırır - bu, 0 (0) List<T>'un son öğesinin doğrudan indekslenmesi için O (1) 'in yerine O (n) olmalıdır.

Standart (Linq) uzantı yöntemleri bunun farkında mı?

C++ 'da STL, yineleyiciler ve niçin tüm bir "kalıtım ağacı" nedeniyle bunun farkındadır.

Answer 1

Sadece son koduna bakmak için reflektörü kullanılmış ve bunun bir IList<T> ilk olup olmadığını görmek için kontrol eder ve (1) çağrısı uygun O gerçekleştirir:

---

DÜZENLEME:

Avukatımın tavsiyesi üzerine kod pasajını reflektörden çıkardım. Kendiniz için kod görmek istiyorsanız ya Reflektör almak ve kendiniz yapın (herkesin sahip olması gereken) ya da daha basitçe bu yazının düzeltme geçmişine bakın (bu konuda yapabileceğim hiçbir şey olmadığından)

(Ya aslında açıkça onu koruyan aynı çatlak yasal ekibi yok kim Mark'ın cevap bakmak)

---

Yani hafif bir döküm yükü değil, numaralandırılırken büyük havai var.

Answer 2

IList<T>'u uygulayan her şey için bir optimizasyon içerir, bu durumda yalnızca öğeyi -1 uzunluğuna bakar.

tüm kod bakamıyor olanlar için IList<T>

uygulamak ... sen gönderecek şeyler büyük çoğunluğu böyle devam IList<T>

List<int> 
int[] 

ve uygulayacak unutmayın

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(); 
     } 


    } 
} 

Çıktı:

onaylamak, sen gözlem ile onaylayabilirsiniz

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

Bu yüzden sadece 30 kat daha yavaştır ve sahip olduğunuz uzunluk listesine sahip performans profilini korur, bu da büyük bir şemada hiçbir şey değildir.

Answer 3

List<T> için O (1) 'dir, ancak diğer numaralar için O (N) olabilir.

Answer 4

sadece :)

Enumerable.Last IList<T> için IEnumerable<T> örneğini downcast çalışır endişelenmeden List<T> ile son kullanabilirsiniz. Bu mümkün ise, indeksleyici ve Count özelliğini kullanır.Reflector gördüğü gibi

İşte uygulamanın bir parçasıdır:

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

Answer 5

Kısa cevap:

O (1).

Açıklama:

O Son() için ListeCount() uzatma yöntemi kullandığı ortada. Sunulursa,

Sayısı() çekler yürütmesinde koleksiyon türü ve Kont özellik kullanır. liste

Sayısı özelliği O (1) karmaşıklığı çok Son() uzatma yöntemi vardır.