Existe uma função limite inferior em um SortedList ?

Question

Existe uma função limite inferior em um SortedList<K ,V>? A função deve retornar o primeiro elemento igual ou maior do que a chave especificada. Existe alguma outra classe que suporta esta?

Caras - leia a pergunta mais uma vez. Eu não preciso de uma função que retorna a chave se ele estiver presente. Estou interessado em cenário quando não há correspondência exata chave.

Estou interessado em O (log n) . Isso significa que eu não tenho um problema com loop foreach, mas gostaria de ter uma maneira eficiente de fazer isso.

Eu fiz alguns testes sobre isso.

declarações Linq não são otimizados por nem o compilador nem máquina de tempo de execução, de modo que percorrer todos os elementos de coleta e são O lento (n). Com base na resposta Mehrdad Afshari, aqui está uma pesquisa binária que as obras em O (log n) sobre a coleção Chaves:

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

busca binária a coleção SortedList.Keys.

Aqui vamos nós. Este é 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

Eu iria com LINQ (presumindo que você estiver usando C # 3), mas usando a sobrecarga de FirstOrDefault que leva um predicado:

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

(um monte de outros métodos Enumerable pode também tomar predicados que é um atalho agradável)

Answer 3

Não tem conhecimento de um, mas é uma simples declaração LINQ:

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

first ou será o primeiro objecto que passa a comparação ou default(T) (que é normalmente null).

Editar

A versão de DaveW:

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

faz o mesmo trabalho, mas poderia ser mais rápido, você teria que testá-lo embora.

Answer 4

Ou você pode escrever próprio método de extensão para fazer isso. Note-se que todas essas funções não são garantidos para ir em uma sequesce.

Answer 5

Esperemos que este deve ser mais rápido, dependendo da implementação do 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;
}