¿Hay una función Límite inferior en un SortedList ?

Question

¿Hay una función Límite inferior en un SortedList<K ,V>? La función debe devolver el primer elemento igual o mayor que la clave especificada. ¿Hay alguna otra clase que apoya esto?

Los chicos - por favor leer la pregunta una vez más. No necesito una función que devuelve la clave si está presente. Estoy interesado en el escenario cuando no hay coincidencia exacta clave.

Estoy interesado en O (log n) . Esto significa que no tengo un problema con bucle foreach, sino gustaría tener una forma eficaz de hacer esto.

He hecho algunas pruebas en este sentido.

declaraciones

Linq no están optimizados ni por el compilador ni máquina de tiempo de ejecución, por lo que caminar a través de todos los elementos de la colección y son O lenta (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 la colección SortedList.Keys.

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

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 3

No es consciente de uno, sino que es una declaración de LINQ simple:

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

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

Editar

La versión de DaveW:

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

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

Answer 4

O puede escribir propio método de extensión para hacer esto. Tenga en cuenta que todas esas funciones no están garantizados para ir en un sequesce.

Answer 5

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