Gibt es eine Lower Bound-Funktion für eine SortedList & lt; K, V & gt;

Gibt es eine Untere Schranke der Funktion auf eine SortedList<K ,V>? Die Funktion sollte das erste element gleich dem oder größer als der angegebene Schlüssel ist. Gibt es eine andere Klasse, die diese unterstützt?

Jungs - bitte lies die Frage noch einmal. Brauche ich nicht als Funktion, liefert den Schlüssel, wenn es vorhanden ist. Ich bin interessiert in Szenario wenn es keine genauen Schlüssel matching.

Ich bin interessiert in O(log n) Zeit. Es bedeutet, dass ich nicht haben ein problem mit einer foreach-Schleife, sondern möchte zu einem effizienten Weg, dies zu tun.

Habe ich einige tests gemacht.

Linq-Anweisungen sind nicht optimiert, weder der compiler noch die Laufzeitumgebung Maschine, so gehen Sie durch alle Elemente aus der Sammlung und langsame O(n). Basierend auf Mehrdad Afshari Antwort, hier ist eine Binäre Suche in O(log n) auf der Keys-Auflistung:

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

InformationsquelleAutor der Frage agsamek | 2009-02-27

  1. 18

    Binäre Suche die SortedList.Keys Sammlung.

    Hier gehen wir. Dies ist in 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);
}

    InformationsquelleAutor der Antwort Mehrdad Afshari

  2. 4

    Ich würde mich mit LINQ (vorausgesetzt, du bist mit C#3), aber durch die überlastung der FirstOrDefault, nimmt ein Prädikat:

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

    (eine Menge von den anderen Enumerable-Methoden können auch Prädikate, die eine nette Abkürzung)

    InformationsquelleAutor der Antwort Dave W

  3. 3

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

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

    first ist entweder das erste Objekt, der vergeht, den Vergleich oder default(T) (in der Regel null).

    Bearbeiten

    DaveW version:

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

    macht die gleiche Arbeit aber potenziell schneller sein, würden Sie haben, um es zu testen obwohl.

    InformationsquelleAutor der Antwort Garry Shutler

  4. -1

    Oder Sie schreiben eigene Erweiterung Methode, dies zu tun. Beachten Sie, dass alle diese Funktionen sind NICHT garantiert, um in einem sequesce.

    InformationsquelleAutor der Antwort Migol

  5. -1

    Hoffentlich schneller sein soll, je nach SortedList Umsetzung.

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

    InformationsquelleAutor der Antwort Shannon Monasco

Schreibe einen Kommentar