O que o .NET Dictionary suporta uma operação de “Chave mais próxima”?

Question

Estou convertendo algum código C ++ em C# e ele chama Std :: map :: Lower_bound (k) para encontrar uma entrada no mapa cuja chave é igual ou maior que k. No entanto, não vejo nenhuma maneira de fazer a mesma coisa com o Dictionário classificado da .NET. Suspeito que eu possa implementar uma solução alternativa usando a lista de classificação, mas infelizmente a lista classificada é muito lenta (o (n) para inserir e excluir chaves). O que posso fazer?

Nota: Encontrei uma solução alternativa usando que tira proveito do meu cenário específico ... especificamente, minhas chaves são uma população densa de números inteiros a partir de pouco mais de 0, então usei uma listau003CTValue> Como meu dicionário com o índice da lista que serve como chave e a busca de uma chave igual ou superior a K pode ser feita em apenas algumas iterações de loop. Mas ainda seria bom ver a pergunta original respondida.

Answer 1

Criei três estruturas de dados relacionadas a árvores B+ que fornecem essa funcionalidade para qualquer tipo de dados: BList<T>, BDictionary<K,V> e BMultiMap<K,V>. Cada uma dessas estruturas de dados fornece FindLowerBound() e FindUpperBound() métodos que funcionam como C ++ 's lower_bound e upper_bound.

Answer 2

Demorou alguns meses de trabalho, mas finalmente posso oferecer pelo menos uma solução parcial para esse problema ... Eu chamo de Trie Compact Patricia, um dicionário classificado que oferece uma operação "encontrar a próxima chave maior".

http://www.codeproject.com/kb/recipes/cptrie.aspx

É apenas uma solução parcial, pois apenas certos tipos de chaves são suportados, ou seja, byte[], string, e todos os tipos inteiros primitivos (int8..uint64). Além disso, a classificação de string é sensível ao minúsculas.

Answer 3

O problema é que uma tabela de dicionário/hash foi projetada para chegar a um local exclusivo da memória com base em um valor de entrada, para que você precise de uma estrutura de dados projetada para acomodar um intervalo relacionado a cada valor que você armazena e no mesmo Atualização de tempo cada intervalo corretamente

Eu penso pular listas (ou árvores binárias equilibradas) podem ajudá -lo. Embora não possam realizar pesquisas em O (n), eles podem fazer logaritmicamente e ainda mais rápido que as árvores.

Sei que essa não é uma resposta adequada, pois não posso dizer que o .NET BCL já contém essa classe, infelizmente você terá que implementar um ou encontrar uma assembléia de terceiros que a apoie para você. Parece haver um bom exemplo em O CodeProject aqui, no entanto.

Answer 4

Você pode tentar o código que escrevi abaixo. Usando pesquisa binária, assumindo, portanto, a lista/matriz é pré-classificada.

public static class ListExtensions
{
    public static int GetAtMostIndex<TItem, TValue>(/*this*/ IList<TItem> list, TValue value, Func<TItem, TValue, int> comparer)
    {
        return GetAtMostIndex(list, value, comparer, 0, list.Count);
    }

    public static int GetAtLeastIndex<TItem, TValue>(/*this*/ IList<TItem> list, TValue value, Func<TItem, TValue, int> comparer)
    {
        return GetAtLeastIndex(list, value, comparer, 0, list.Count);
    }

    public static int GetAtMostIndex<TItem, TValue>(/*this*/ IList<TItem> list, TValue value, Func<TItem, TValue, int> comparer, int index, int count)
    {
        if (count == 0)
        {
            return -1;
        }

        int startIndex = index;
        int endIndex = index + count - 1;
        int middleIndex = 0;
        int compareResult = -1;

        while (startIndex < endIndex)
        {
            middleIndex = (startIndex + endIndex) >> 1; //  / 2
            compareResult = comparer.Invoke(list[middleIndex], value);

            if (compareResult > 0)
            {
                endIndex = middleIndex - 1;
            }
            else if (compareResult < 0)
            {
                startIndex = middleIndex + 1;
            }
            else
            {
                return middleIndex;
            }
        }

        if (startIndex == endIndex)
        {
            compareResult = comparer.Invoke(list[startIndex], value);

            if (compareResult <= 0)
            {
                return startIndex;
            }
            else
            {
                int returnIndex = startIndex - 1;

                if (returnIndex < index)
                {
                    return -1;
                }
                else
                {
                    return returnIndex;
                }
            }
        }
        else
        {
            //todo: test
            return startIndex - 1;
        }
    }

    public static int GetAtLeastIndex<TItem, TValue>(/*this*/ IList<TItem> list, TValue value, Func<TItem, TValue, int> comparer, int index, int count)
    {
        if (count == 0)
        {
            return -1;
        }

        int startIndex = index;
        int endIndex = index + count - 1;
        int middleIndex = 0;
        int compareResult = -1;

        while (startIndex < endIndex)
        {
            middleIndex = (startIndex + endIndex) >> 1; //  / 2
            compareResult = comparer.Invoke(list[middleIndex], value);

            if (compareResult > 0)
            {
                endIndex = middleIndex - 1;
            }
            else if (compareResult < 0)
            {
                startIndex = middleIndex + 1;
            }
            else
            {
                return middleIndex;
            }
        }

        if (startIndex == endIndex)
        {
            compareResult = comparer.Invoke(list[startIndex], value);

            if (compareResult >= 0)
            {
                return startIndex;
            }
            else
            {
                int returnIndex = startIndex + 1;

                if (returnIndex >= index + count)
                {
                    return -1;
                }
                else
                {
                    return returnIndex;
                }
            }
        }
        else
        {
            return endIndex + 1;
        }
    }
}

Answer 5

Encontre mais próximo de K:

dict.Keys.Where(i => i >= K).OrderBy(i => i).First();

ou muito mais rápido:

public int? GetNearestKey(dict, K) 
{
    int? lowerK = null;
    foreach (int key in dict.Keys)
    {
        if (key == K) 
        {
            lowerK = K;
            break; 
        }
        else if (key >= K && (!lowerK.HasValue || key < lowerK))
        {
            lowerK = key;
        }
    }
    return lowerK;
}

Answer 6

Não há uma implementação de coleta de árvores de pesquisa binária na estrutura base, então você precisará criar um ou encontrar uma implementação. Como você observou, a lista classificada é mais próxima em termos de pesquisa, mas é mais lenta (devido à sua implementação de matriz subjacente) para inserção/exclusão.

Answer 7

Eu acho que há um erro na pergunta sobre Lista classificada complexidade.

Lista classificada tem complexidade amortizada O (log (n)) para inserção novo item. Se você souber com antecedência a capacidade, isso pode ser feito em O (log (n)) no pior dos casos.

Answer 8

Você pode fazer isso por SortedSet<T> com os seguintes métodos de extensão:

public static class SortedSetExtensions
{
    public static bool FindLowerOrEqualThan<T>(this SortedSet<T> set, T value, out T first)
    {
        if(set.Count == 0)
        {
            first = default(T);
            return false;
        }

        var minimum = set.Min;

        if(set.Comparer.Compare(minimum, value) > 0)
        {
            first = default(T);
            return false;
        }

        first = set.GetViewBetween(minimum, value).Max;
        return true;
    }

    public static bool FindGreaterOrEqualThan<T>(this SortedSet<T> set, T value, out T first)
    {
        if (set.Count == 0)
        {
            first = default(T);
            return false;
        }

        var maximum = set.Max;

        if (set.Comparer.Compare(maximum, value) < 0)
        {
            first = default(T);
            return false;
        }

        first = set.GetViewBetween(value, maximum).Min;
        return true;
    }
}