Gibt es eine untere Grenze Funktion auf einem SortedList ?

Question

Gibt es eine untere Grenze Funktion auf einem SortedList<K ,V>? Die Funktion sollte das erste Element gleich oder größer als der angegebenen Schlüssel zurück. Gibt es eine andere Klasse, die diese unterstützt?

Guys - bitte die Frage noch einmal lesen. Ich brauche nicht eine Funktion, die den Schlüssel zurückgibt, wenn es vorhanden ist. Ich bin in Szenario interessiert, wenn es keine genaue Tastenanpassung ist.

Ich habe Interesse an O (log n) Zeit . Es bedeutet, dass ich kein Problem mit foreach-Schleife habe, sondern möchte eine effiziente Möglichkeit haben, dies zu tun.

Ich habe einige Tests auf das getan.

Linq Aussagen sind nicht durch weder Compiler noch Laufzeitmaschine optimiert, so dass sie gehen durch alle Sammelelemente und sind langsam O (n). Basierend auf Mehrdad Afshari Antwort, hier ist eine binäre Suche, die in O (log n) auf der Keys-Auflistung funktioniert:

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

Binary-Suche SortedList.Keys Sammlung.

Hier gehen wir. Dies ist O (log 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

ich mit LINQ gehen würde (vorausgesetzt, Sie C # 3 verwenden), aber die Überlastung von FirstOrDefault verwenden, die ein Prädikat nimmt:

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

(viele der anderen Enumerable Methoden können auch Prädikate nehmen, die eine nette Abkürzung ist)

Answer 3

Nicht bewusst, aber es ist eine einfache LINQ-Anweisung:

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

first wird entweder das erste Objekt sein, das den Vergleich oder default(T) gibt (die normalerweise null ist).

Bearbeiten

davew Version:

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

macht die gleiche Arbeit, aber potenziell schneller sein könnten, würden Sie es allerdings testen.

Answer 4

Sie können auch eigene Erweiterungsmethode schreiben, dies zu tun. Beachten Sie, dass alle diese Funktionen sind nicht in der sequesce gehen garantiert.

Answer 5

Hoffentlich sollte schneller sein, je nach SortedList-Implementierung.

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