Sıralama düzenini koruyan koleksiyon C#

Question

Nesnelerin bir listesini içeren Foo sınıfına sahibim: List<Bar>. Her bir Bar, sipariş edilebilecekleri bir süreye sahiptir (bir süreyi temsil eden TimeSpan tipinde) ve Bar, değişmez bir nesnedir - yani, algoritmanın çalışması boyunca süre değişmez. Şu anda, her bir Foo için, eğer sipariş verildiyse (yani en kısa süre için Bar), listede ilk olacak olan Bar'u koruyorum. Böyle bir şey performans (hız) işlem burada

public class Foo 
{ 
    public List<Bar> AllBars { get; set; } 

    public Bar FirstBar { get; set; } 

    public Foo (Bar bar) 
    { 
     FirstBar = bar; 

     AllBars = new List<Bar>() { bar }; 
    } 

    public AddBar(Bar bar) 
    { 
     if(bar.Duration < FirstBar.Duration) 
     { 
      FirstBar = bar; 
     } 

     AllBars.Add(bar); 
    } 
} 

Bu sınıf Foo bir algoritma kullanılır kritiktir. Hafıza önemli ama hız kadar değil. Her biri en fazla m s'ye sahip olan n s listesi bulunmaktadır. Bu sınıf bana bu noktaya kadar iyi hizmet etti. Şimdi kullanıcıya birkaç seçenek sunmak istiyorum, yani listedeki ilk birkaç Bar s rasgele erişime ihtiyacım olacak.

Bu nedenle sırayla dizine göre erişebilmem için Bar s numaramı saklamak istiyorum. Bar sınıfımda, Bar s süreleri karşılaştırıldığında karşılaştırmak için IComparable uyguladı, ancak uygun bir veri türü seçerken takılıyorum. System.Collections.SortedList'a baktım ama (yanılmadıkça) bu, IDictionary'u uyguladığı şekilde, öğelere göre referans öğeleri olarak görünüyor. Nesneleri dizilenecek şekilde koruyacak ve dizin sırasına göre hareket edebilecek şekilde hangi koleksiyonu kullanabilirdim?

Answer 1

(asker talep ettiği, bir yorumu da terfi).

yourSortedList.Add(yourBar, null) ile O (n) zamanında ekleyin (listenin eklediğiniz noktadan sonra tüm girişleri "yukarı" taşıması gerekir). yourSortedList.Keys[i] ile i inci girişini O (1) zamanında alın.

Yukarıdaki açıklamanın doğru olduğunu "kanıt" için SortedList<,>.Keys property documentation'a bakın. Bir SortedList<,>'un aslında bir "liste" 'den (yani, gerektiğinde daha büyük bir dizi ile yer değiştirmeye tabi olarak Capacity uzunluğunda bir dizi) oluştuğunu unutmayın. Bu, ikili bir arama ağacı olduğuna inandığım SortedDictionary<,>'dan farklıdır.

Not Ancak: listenize SortedList<,> çiftleri olması mümkün olmayacaktır, bu yüzden listede iki üye dönüş değeri sıfır olan CompareTo birbirine izin verilmez.

Answer 2

Anahtar ve değerin aynı nesne olduğu ikili bir ağaç olan SortedSet<T> kullanmayı tercih ederim. Bu bir kez daha ekleme/çıkarma/aramaların logaritmik - O(log n) - olduğu anlamına gelir, ancak sırayla öğeleri yineleme yeteneğini kazanırsınız. Bu koleksiyonun etkili olabilmesi için, T tipi IComparable<T>'u uygulamalıdır veya harici bir IComparer<T> sağlamanız gerekir.

Answer 3

Neden sadece List.Insert kullanıyorsunuz?
Ek, O (n) şeklindedir ve belirli bir dizine ekleyebilmenizi sağlar.
n + n hala O (n)

public AddBar(Bar bar) 
{ 
    int index = 0;  
    foreach (bar b in AllBar) 
    { 
     if(bar.Duration < b.Duration) 
     break; 
     index++; 
    } 
    AllBars.Insert(index, bar); 
} 

Yani sıralama var ve O (1) endeks O bir maliyetle
(n)
ekle akım (n) da O ekle olduğu

A NlogN içinde SortedList ve anahtar Süre olup eşsiz

A SortedSet eki anahtar logn ama bir ToList o (n) yani hala Ç gibi o zaman (index yok n)

Listede sıralama yöntemini çağırma

Bu, belirtilen soruya cevap verir NlogN

geçerli: Sanırım bu onların sıralanmış halde kalmasını şekilde benim nesneleri korumak ve bu tür onlar düzen içinde traversable olduklarını ediyorum kullanabilirsiniz hangi koleksiyon indeks?

Bunu O (n) Ekle'den daha iyi bir şekilde yapacağınızı düşünmüyorum.
Kim daha önce bir oy vermişse o zaman daha iyi bir çözüm nedir? Eğer değer bölümünü kullanmayın nerede sadece SortedList<Bar, object> kullanın hiçbir şey ifade "değerleri" olan yaşayabilirsen