linkedlist - sortedlist en c#

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

Question

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

Chicos, por favor lean la pregunta una vez más. No necesito una función que devuelva la clave si está presente. Me interesa el escenario cuando no hay una coincidencia de clave exacta.

Estoy interesado en O (log n) tiempo . Significa que no tengo un problema con el bucle foreach, sino que me gustaría tener una forma eficiente de hacerlo.

He hecho algunas pruebas sobre esto.

Las declaraciones de Linq no están 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 O (n) lentos. En base a la respuesta de Mehrdad Afshari, aquí hay una búsqueda binaria que funciona en O (log n) en la colección de claves:

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 busca la colección 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

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

Answer 3

Iría con LINQ (suponiendo que estés usando C # 3), pero usando la sobrecarga de FirstOrDefault que toma un predicado:

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

(muchos de los otros métodos Enumerables también pueden tomar predicados, lo que es un buen atajo)

Answer 4

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

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

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

Editar

La versión de DaveW:

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

hace el mismo trabajo, pero podría ser más rápido, aunque tendrías que probarlo.

Answer 5

O puedes escribir un método de extensión propio para hacer esto. Tenga en cuenta que NO se garantiza que todas esas funciones vayan en una secuencia.