SortedList <K ,V>'da Alt Sınır işlevi var mı?

Question

SortedList<K ,V>'da Alt Sınır işlevi var mı? Fonksiyon, ilk elemanı belirtilen anahtara eşit veya daha büyük olana döndürmelidir. Bunu destekleyen başka bir sınıf var mı?

Çocuklar - lütfen soruyu bir kez daha okuyun. Varsa anahtarı döndüren bir işleve ihtiyacım yok. Kesin anahtar eşleşmesi olmadığında senaryoya ilgi duyuyorum.

O (log n) saat ile ilgileniyorum. Bu, foreach döngüsüyle ilgili bir problemim olmadığı anlamına geliyor, bunun yerine bunu yapmanın verimli bir yoluna sahip olmak istiyor.

Bu konuda bazı testler yaptım.

Linq ifadeleri ne derleyici ne de çalışma zamanı makinesi tarafından optimize edilmez, bu nedenle tüm koleksiyon öğeleri arasında gezinirler ve yavaşça O (n) olurlar.

public static int FindFirstIndexGreaterThanOrEqualTo<T>(
      this IList<T> sortedCollection, T key 
     ) where T : IComparable<T> { 
    int begin = 0; 
    int end = sortedCollection.Count; 
    while (end > begin) { 
     int index = (begin + end)/2; 
     T el = sortedCollection[index]; 
     if (el.CompareTo(key) >= 0) 
      end = index; 
     else 
      begin = index + 1; 
    } 
    return end; 
} 

Answer 1

İkili SortedList.Keys toplama arama: Mehrdad Afshari cevap dayanarak, burada Tuşlar koleksiyonunda (n günlük) O çalışan bir ikili arama olduğunu.

İşte başlıyoruz. birinin

private static int BinarySearch<T>(IList<T> list, T value) 
{ 
    if (list == null) 
     throw new ArgumentNullException("list"); 
    var comp = Comparer<T>.Default; 
    int lo = 0, hi = list.Count - 1; 
    while (lo < hi) { 
      int m = (hi + lo)/2; // this might overflow; be careful. 
      if (comp.Compare(list[m], value) < 0) lo = m + 1; 
      else hi = m - 1; 
    } 
    if (comp.Compare(list[lo], value) < 0) lo++; 
    return lo; 
} 

public static int FindFirstIndexGreaterThanOrEqualTo<T,U> 
          (this SortedList<T,U> sortedList, T key) 
{ 
    return BinarySearch(sortedList.Keys, key); 
} 

Answer 2

farkında değil, ama basit bir LINQ ifadesi var: Bu O (n log)

first = sortedList.Where(x => x >= theObjectForComparison).FirstOrDefault(); 

first olacak ya karşılaştırma veya default(T) geçer birinci nesneyi olmak (normal olarak null).

Düzenleme

DaveW versiyonu:

first = sortedList.FirstOrDefault(x => x >= theObjectForComparison); 

aynı işi yapar ama potansiyel olarak daha hızlı olabilir, gerçi bunu test etmek gerekir.

Answer 3

LINQ gelirdim (kullandığınız varsayarak C# 3), ancak bir yüklemi alır FirstOrDefault aşırı yüklenmesini kullanarak:

first = sortedList.FirstOrDefault(x => x >= theObjectForComparison); 

(diğer Enumerable yöntemlerden çok da alabilir

Answer 4

Ya da bunu yapmak için kendi uzantı yöntemini yazabilirsiniz. Tüm bu fonksiyonların bir sekmeye girme garantisi olmadığını unutmayın.

Answer 5

Bu, SortedList uygulamasına bağlı olarak daha hızlı olmalı.

public static int FindFirstIndexGreaterThanOrEqualTo<K, V>(
     this SortedList<K, V> sortedCollection, K key 
    ) where V : new() 
{ 
    if (sortedCollection.ContainsKey(key)) 
    { 
     return sortedCollection.IndexOfKey(key); 
    } 
    sortedCollection[key] = new V(); 
    int retval = sortedCollection.IndexOfKey(key); 
    sortedCollection.Remove(key); 
    return retval; 
}