Y at-il une fonction de limite inférieure sur une SortedList ?

Question

Y at-il une fonction minorant un SortedList<K ,V>? La fonction doit renvoyer le premier élément est égal ou supérieur à la clé spécifiée. Y at-il une autre classe qui prend en charge cela?

Les gars - s'il vous plaît lire la question une fois de plus. Je ne suis pas besoin d'une fonction qui retourne la clé si elle est présente. Je suis intéressé par le scénario quand il n'y a pas de correspondance exacte clé.

Je suis intéressé par O (log n) . Cela signifie que je n'ai pas de problème avec boucle foreach, mais voudrais plutôt avoir un moyen efficace de le faire.

Je l'ai fait quelques tests sur ce point.

déclarations Linq ne sont pas optimisés ni par le compilateur ni la machine d'exécution, ils marchent à travers tous les éléments de collecte et sont O lente (n). Sur la base de réponse Mehrdad Afshari, voici une recherche binaire qui fonctionne en O (log n) sur la collection Touches:

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 recherche la collection SortedList.Keys.

On y va. Ceci est 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

Je vais avec LINQ (en supposant que vous utilisez C # 3), mais en utilisant la surcharge de FirstOrDefault qui prend un prédicat:

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

(beaucoup des autres méthodes Enumerable peut également prendre prédicats qui est un raccourci bien)

Answer 3

Pas au courant d'un, mais il est une simple déclaration de LINQ:

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

first sera soit le premier objet qui transmet la comparaison ou default(T) (qui est normalement null).

Modifier

La version de DaveW:

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

fait le même travail, mais pourrait être plus rapide, vous auriez à le tester si.

Answer 4

Ou vous pouvez écrire propre méthode d'extension pour le faire. Notez que toutes ces fonctions ne sont pas garanties pour aller dans un sequesce.

Answer 5

Espérons que cela devrait être plus rapide, en fonction de la mise en œuvre de 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;
}