SortedList<K ,V> に Lower Bound 関数はありますか?

StackOverflow https://stackoverflow.com/questions/594518

  •  09-09-2019
  •  | 
  •  

質問

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

皆さん、もう一度質問を読んでください。 キーが存在する場合、キーを返す関数は必要ありません。正確に一致するキーがない場合のシナリオに興味があります。

O(log n) 時間に興味があります. 。これは、foreach ループに問題があるのではなく、これを効率的に実行する方法が必要であることを意味します。

これに関していくつかのテストを行ってきました。

Linq ステートメントはコンパイラーでもランタイム マシンでも最適化されないため、すべてのコレクション要素を処理し、O(n) が遅くなります。Mehrdad Afshari の回答に基づいて、Keys コレクションに対して O(log 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;
}
役に立ちましたか？

解決

二分探索 SortedList.Keys コレクション。

さぁ行こう。これは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);
}

他のヒント

私は LINQ を使用します (C#3 を使用していると仮定します)。ただし、述語を取る FirstOrDefault のオーバーロードを使用します。

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

(他の多くの Enumerable メソッドも述語を取ることができ、これは優れたショートカットです)

あまり知られていませんが、これは単純な LINQ ステートメントです。

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

first 比較に合格した最初のオブジェクトになるか、 default(T) (通常は null).

編集

DaveW のバージョン:

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

同じ仕事をしますが、潜在的に高速になる可能性があります。ただし、テストする必要があります。

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

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;
}
ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top