¿Hay una función de límite inferior en una SortedList <K ,V>?

Question

¿Hay una función de límite inferior en SortedList<K ,V>? La función debe devolver el primer elemento igual o superior a la clave especificada. ¿Hay alguna otra clase que apoye esto?

Chicos - por favor lea la pregunta una vez más. No necesito una función que devuelva la clave si está presente. Me interesa el escenario cuando no coinciden las claves exactas.

Me gusta 0 (horario de verano). Significa que no tengo un problema con foreach loop, pero me gustaría tener una forma eficiente de hacerlo.

He hecho algunas pruebas al respecto.

Las sentencias de Linq no son optimizadas ni por el compilador ni por la máquina de tiempo de ejecución, por lo que recorren todos los elementos de la colección y son lentos O (n). Sobre la base de la respuesta Mehrdad Afshari, aquí es una búsqueda binaria que funciona en O (log n) en la Recogida de llaves:

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

binario Buscar en toda la SortedList.Keys.

Aquí vamos. Esto es 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

no tiene conocimiento de uno, pero es una declaración LINQ simple:

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

first bien será el primer objeto que pasa la comparación o default(T) (que normalmente es null).

Editar

versión de DaveW:

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

hace el mismo trabajo, pero potencialmente podría ser más rápido, que tendría que probarlo sin embargo.

Answer 3

me gustaría ir con LINQ (suponiendo que estés usando C# 3), pero utilizando la sobrecarga de FirstOrDefault que tiene un predicado:

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

(muchos de los otros métodos enumerables también puede tomar predicados que es un buen atajo)

Answer 4

O puede escribir su propio método de extensión para hacer esto. Tenga en cuenta que no se garantiza que todas esas funciones entren en un enclaustramiento.

Answer 5

Esperemos que esto debería ser más rápido, dependiendo de la implementación 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; 
}