SortedList <K ,V>に下限関数がありますか？

Question

SortedList<K ,V>に下限機能がありますか？この関数は、指定されたキー以上の最初の要素を返す必要があります。これをサポートする他のクラスがありますか？

みんな - もう一度質問をお読みください。 キーがある場合は、キーを返す関数は必要ありません。正確なキーマッチングがない場合のシナリオに興味があります。

私はO（log n）時間に興味があります。これはforeachループで問題がないことを意味しますが、これを行う効率的な方法を望みます。

私はこれについていくつかのテストを行いました。

Linq文は、コンパイラもランタイムマシンも最適化されていないため、すべてのコレクション要素を処理し、遅いO（n）です。

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

バイナリSortedList.Keysコレクションを検索：Mehrdad Afshariの回答に基づいて、ここでキーコレクションで（nはログ）Oで働くバイナリ検索です。

ここに移動します。これは、O（Nを記録）である：

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

ない1を認識して、それは、単純なLINQステートメントの：

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

firstは、（最初​​の比較を渡すオブジェクトまたはdefault(T)のどちらかになりますこれは通常nullです）。

編集

DaveWのバージョン：

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

が同じ仕事をしていませんが、潜在的に速くなる可能性があり、あなたががそれをテストする必要があると思います。

Answer 3

私はLINQで行くと思います（使用している前提C＃3）が、述語を取るFirstOrDefaultのオーバーロードを使用して：

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

（他の可算方法の多くも取ることができます述語は素敵なショートカットです）

Answer 4

またはこれを行う独自の拡張メソッドを書くことができます。これらすべての機能は、連続して動作することは保証されていないことに注意してください。

Answer 5

SortedListの実装に応じて、これは高速になるはずです。

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