Árvores Binárias e Dicionários C#

StackOverflow https://stackoverflow.com/questions/2151747

Pergunta

Estou lutando com o conceito de quando usar árvores de pesquisa binária e quando usar dicionários.

Na minha aplicação fiz um pequeno experimento que utilizou a biblioteca C5 TreeDictionary (que acredito ser uma árvore de pesquisa binária vermelha e preta) e o dicionário C#.O dicionário sempre foi mais rápido nas operações de adição/localização e também sempre usou menos espaço de memória.Por exemplo, em 16809 <int, float> entradas, o dicionário usou 342 KiB enquanto a árvore usou 723 KiB.

Achei que os BST deveriam ser mais eficientes em termos de memória, mas parece que um nó da árvore requer mais bytes do que uma entrada em um dicionário.O que da?Existe um ponto em que os BST são melhores que os dicionários?

Além disso, como pergunta paralela, alguém sabe se existe uma estrutura de dados mais rápida e com maior eficiência de memória para armazenar <int, float> pares para acesso ao tipo de dicionário do que qualquer uma das estruturas mencionadas?

Foi útil?

Solução

Eu pensei que os BSTs deveriam ser mais eficientes em memória, mas parece que um nó da árvore requer mais bytes do que uma entrada em um dicionário.O que da?Existe um momento em que os BSTs são melhores que os dicionários?

Pessoalmente, nunca ouvi falar de tal princípio.Mesmo assim, é apenas um princípio geral, não um fato categórico gravado na estrutura do universo.

Geralmente, os dicionários são apenas um invólucro sofisticado em torno de uma série de listas vinculadas.Você insere no dicionário algo como:

LinkedList<Tuple<TKey, TValue>> list =
    internalArray[internalArray % key.GetHashCode()];
if (list.Exists(x => x.Key == key))
    throw new Exception("Key already exists");
list.AddLast(Tuple.Create(key, value));

Então é aproximadamente O(1) operação.O dicionário usa memória O(internalArray.Length + n), onde n é o número de itens na coleção.

Em geral, os BSTs podem ser implementados como:

  • listas vinculadas, que usam espaço O(n), onde n é o número de itens na coleção.
  • matrizes, que usa O(2h - n) espaço onde h é a altura da árvore en é o número de itens da coleção.
    • Como as árvores rubro-negras têm uma altura limitada de O(1,44 * n), uma implementação de array deve ter um uso de memória limitado de cerca de O(21,44n - n)

As probabilidades são de que o TreeDictionary C5 seja implementado usando arrays, o que provavelmente é responsável pelo espaço desperdiçado.

O que da?Existe um momento em que os BSTs são melhores que os dicionários?

Os dicionários têm algumas propriedades indesejáveis:

  • Pode não haver blocos contínuos de memória suficientes para armazenar seu dicionário, mesmo que os requisitos de memória sejam muito menores que o total de RAM disponível.

  • Avaliar a função hash pode levar um período de tempo arbitrariamente longo.Strings, por exemplo, usam o Reflector para examinar o System.String.GetHashCode método - você notará que o hash de uma string sempre leva tempo O(n), o que significa que pode levar um tempo considerável para strings muito longas.Por outro lado, comparar strings quanto à desigualdade é quase sempre mais rápido do que fazer hash, pois pode exigir a observação apenas dos primeiros caracteres.É totalmente possível que as inserções de árvore sejam mais rápidas que as inserções de dicionário se a avaliação do código hash demorar muito.

    • Int32 GetHashCode método é literalmente apenas return this, então seria difícil encontrar um caso em que uma tabela hash com chaves int seja mais lenta que um dicionário de árvore.

As árvores RB têm algumas propriedades desejáveis:

  • Você pode encontrar/remover os elementos Min e Max em tempo O(log n), comparado ao tempo O(n) usando um dicionário.

  • Se uma árvore for implementada como uma lista vinculada em vez de um array, a árvore será geralmente mais eficiente em termos de espaço do que um dicionário.

  • Da mesma forma, é ridiculamente fácil escrever versões imutáveis ​​de árvores que suportam inserção/pesquisa/exclusão em tempo O (log n).Os dicionários não se adaptam bem à imutabilidade, pois é necessário copiar todo o array interno para cada operação (na verdade, eu ter vi algumas implementações baseadas em array de árvores de dedos imutáveis, uma espécie de estrutura de dados de dicionário de uso geral, mas a implementação é muito complexa).

  • Você pode percorrer todos os elementos em uma árvore em ordem de classificação em espaço constante e tempo O(n), enquanto seria necessário despejar uma tabela hash em uma matriz e classificá-la para obter o mesmo efeito.

Portanto, a escolha da estrutura de dados realmente depende de quais propriedades você precisa.Se você deseja apenas uma sacola não ordenada e pode garantir que sua função hash seja avaliada rapidamente, escolha um Dicionário .Net.Se você precisar de uma sacola ordenada ou tiver uma função hash lenta, use TreeDictionary.

Outras dicas

Faz sentido que um nó de árvore exigisse mais armazenamento do que uma entrada de dicionário. Um nó da árvore binária precisa armazenar o valor e as subárvores esquerda e direita. O genérico Dictionary<TKey, TValue> é implementado como uma tabela de hash que - estou assumindo - usa uma lista vinculada para cada balde (valor mais um ponteiro/referência) ou algum tipo de remapeamento (apenas o valor). Eu teria que dar uma olhada no refletor para ter certeza, mas para os propósitos desta pergunta, não acho que seja tão importante.

A tabela mais escassa da hash, menos eficiente em termos de armazenamento/memória. Se você criar uma tabela de hash (dicionário) e inicializar sua capacidade para 1 milhão e preencher apenas 10.000 elementos, tenho certeza de que ele consumiria muito mais memória do que um BST com 10.000 nós.

Ainda assim, eu não me preocuparia com isso se a quantidade de nós/chaves estivesse apenas aos milhares. Isso será medido nos Kilobytes, em comparação com os gigabytes de RAM física.

Se a pergunta é "Por que você gostaria de usar uma árvore binária em vez de uma mesa de hash?" Então a melhor resposta IMO é que as árvores binárias são ordenadas enquanto as tabelas de hash não são. Você só pode pesquisar uma tabela de hash por chaves exatamente iguais a algo; Com uma árvore, você pode procurar uma variedade de valores, valor mais próximo, etc. Essa é uma distinção muito importante se estiver criando um índice ou algo semelhante.

Parece -me que você está fazendo uma otimização prematura.

O que eu sugiro para você é criar uma interface para isolar qual estrutura você está realmente usando e, em seguida, implementar a interface usando o dicionário (que parece funcionar melhor).

Se a memória/desempenho se tornar um problema (o que provavelmente não será de 20k-números), você poderá criar outras implementações de interface e verificar qual é o melhor. Você não precisará alterar quase nada no restante do código (exceto qual implementação está usando).

A interface para uma árvore e uma tabela de hash (que eu acho que é o que seu dicionário é baseado) deve ser muito semelhante. Sempre girando em torno de pesquisas com chave.

Eu sempre pensei que um dicionário era melhor para criar coisas uma vez e depois fazer muitas pesquisas nele. Enquanto uma árvore era melhor se você o estivesse modificando significativamente. No entanto, não sei de onde eu escolhi essa ideia.

(Os idiomas funcionais geralmente usam árvores como base para as coleções, pois você pode reutilizar a maior parte da árvore se fizer pequenas modificações).

Você não está comparando "maçãs com maçãs", um BST lhe dará um ordenado Representação enquanto um dicionário permite fazer uma pesquisa em um par de valores -chave (no seu caso).

Eu não esperaria muito tamanho na pegada de memória entre os 2, mas o dicionário lhe dará uma pesquisa muito mais rápida. Para encontrar um item em um BST, você (potencialmente) precisa atravessar toda a árvore. Mas, para fazer uma pesquisa dictnary, você simplesmente procure com base na chave.

Um BST equilibrado é preferível se você precisar proteger sua estrutura de dados contra picos de latência e ataques de colisões de hash.

O primeiro acontece quando uma estrutura apoiada por matriz cresce e é redimensionada, o último é uma propriedade inevitável do algoritmo de hash como uma projeção do espaço infinito para uma faixa inteira limitada.

Outro problema no .NET é que existe Loh e, com um dicionário suficientemente grande, você encontra uma fragmentação de LOH. Nesse caso, você pode usar um BST, pagando um preço de maior classe de complexidade algorítmica.

Em suma, com um BST apoiado pela pilha de alocação, você obtém o pior caso O (log (n)), com a hashtable você obtém o (n) pior do momento.

O BST tem um preço médio de O (log (n)), a pior localidade do cache e mais alocações de heap, mas possui garantias de latência e é protegido contra ataques de dicionário e fragmentação da memória.

Vale a pena notar que o BST também é sujeito à fragmentação da memória em outras plataformas, não usando um coletor de lixo compacto.

Quanto ao tamanho da memória, a classe .NET Dictionary`2 é mais eficiente na memória, porque armazena dados como uma lista vinculada fora da heap, que armazena apenas informações de valor e compensação. O BST precisa armazenar o cabeçalho do objeto (como cada nó é uma instância de classe na pilha), dois ponteiros e alguns dados de árvores aumentados para árvores equilibradas. Por exemplo, uma árvore vermelha-preta precisaria de um booleano interpretado como cor (vermelho ou preto). São pelo menos 6 palavras da máquina, se não me engano. Portanto, cada nó em uma árvore preto em sistema de 64 bits é um mínimo de:

3 palavras para o cabeçalho = 24 bytes 2 palavras para os ponteiros da criança = 16 bytes 1 palavra para a cor = 8 bytes pelo menos 1 palavra para o valor 8+ bytes = 24+16+8 = 8 = 56 bytes (+8 bytes Se a árvore usar um ponteiro de nó pai).

Ao mesmo tempo, o tamanho mínimo da entrada do dicionário seria de apenas 16 bytes.

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top