Y at-il une fonction de limite inférieure sur une liste triée <K ,V>?

Question

Y a-t-il une fonction de limite inférieure sur un SortedList<K ,V>? La fonction doit renvoyer le premier élément égal ou supérieur à la clé spécifiée. Y a-t-il une autre classe qui supporte cela?

Gars - veuillez relire la question encore une fois. Je n'ai pas besoin d'une fonction qui retourne la clé si elle est présente. Je suis intéressé par le scénario lorsqu'il n'y a pas de correspondance exacte des clés.

Je suis intéressé par O (log n) temps. Cela signifie que je n'ai pas de problème avec foreach loop, mais que je préfère avoir un moyen efficace de le faire.

J'ai fait quelques tests à ce sujet.

Les instructions Linq ne sont optimisées ni par le compilateur ni par la machine d'exécution, elles passent donc par tous les éléments de la collection et sont O (n) lents. Sur la base de Mehrdad Afshari réponse, voici une recherche binaire qui fonctionne en O (log n) sur la collection Clés:

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

recherche binaire la collection SortedList.Keys.

Nous y voilà. 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

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 passe la comparaison ou default(T) (qui est normalement null).

Modifier

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 3

je partirais 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 predicates qui est un raccourci sympa)

Answer 4

Ou vous pouvez écrire votre propre méthode d'extension pour ce faire. Notez que toutes ces fonctions ne sont pas garanties d'entrer dans un séquestre.

Answer 5

Espérons que cela devrait être plus rapide, en fonction de l'implémentation 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; 
}