Quais são as estruturas de dados menos conhecidas, mas úteis?

Existem algumas estruturas de dados que são realmente úteis, mas são desconhecidas para a maioria dos programadores. Quais são eles?

Todo mundo sabe sobre listas vinculadas, árvores binárias e hashes, mas e as listas Skip e Bloom, por exemplo. Gostaria de conhecer mais estruturas de dados que não são tão comuns, mas valem a pena conhecer, porque elas se baseiam em grandes idéias e enriquecem a caixa de ferramentas de um programador.

PS: Também estou interessado em técnicas como links de dança que fazem uso inteligente das propriedades de uma estrutura de dados comum.

EDIT : Tente incluir links para páginas que descrevem as estruturas de dados em mais detalhes. Além disso, tente adicionar algumas palavras sobre por que uma estrutura de dados é legal (como Jonas Kölker já apontou). Além disso, tente fornecer uma estrutura de dados por resposta . Isso permitirá que as melhores estruturas de dados flutuem para o topo com base apenas em seus votos.

As tentativas , também conhecidas como árvores prefixadas ou críticas , existem há mais de 40 anos, mas ainda são relativamente desconhecidas. Um uso muito interessante das tentativas é descrito em " TRASH - Uma estrutura dinâmica de dados LC-trie e hash ", que combina uma tentativa com uma função hash.

Filtro Bloom : matriz de bits de m bits, inicialmente definida como 0.

Para adicionar um item, execute-o por meio de funções k hash que fornecerão k índices na matriz que você definirá como 1.

Para verificar se um item está no conjunto, calcule os índices k e verifique se estão todos definidos como 1.

Obviamente, isso dá alguma probabilidade de falsos positivos (de acordo com a Wikipedia é de cerca de 0,61 ^ (m / n), em que n é o número de itens inseridos). Falsos negativos não são possíveis.

A remoção de um item é impossível, mas você pode implementar o filtro de contagem florido , representado pela matriz de entradas e incremento / decremento.

Corda : é uma string que permite prepends, substrings, inserções intermediárias e anexos baratos. Eu realmente só o usei uma vez, mas nenhuma outra estrutura seria suficiente. Anexos regulares de strings e matrizes eram muito caros para o que precisávamos fazer, e reverter tudo estava fora de questão.

As listas de pulos são bem legais.

Wikipedia
Uma lista de ignorados é uma estrutura de dados probabilística, baseada em várias listas vinculadas paralelas e ordenadas, com eficiência comparável a uma árvore de pesquisa binária (log de pedidos n tempo médio para a maioria das operações).

Eles podem ser usados ​​como uma alternativa às árvores balanceadas (usando o balanceamento probalístico em vez da imposição rigorosa do balanceamento). Eles são fáceis de implementar e mais rápidos do que, digamos, uma árvore vermelha-preta. Eu acho que eles deveriam estar em todos os bons programas de ferramentas de programação.

Se você deseja obter uma introdução aprofundada às listas de pulos, aqui está um link para um vídeo da palestra Introdução aos algoritmos do MIT sobre eles.

Além disso, aqui está um applet Java demonstrando visualmente as Listas de ignoradas.

Os índices espaciais , em particular as árvores R e KD , armazenam dados espaciais com eficiência. Eles são bons para dados de coordenadas de mapas geográficos e algoritmos de local e rota VLSI e, às vezes, para pesquisa de vizinhos mais próximos.

Matrizes de bits armazenam bits individuais compactamente e permitem operações rápidas de bits.

Zíperes - derivados de estruturas de dados que modificam a estrutura para ter uma noção natural de 'cursor' - local atual. Eles são realmente úteis, pois garantem que as indicações não podem estar fora do limite - usadas, por exemplo, no gerenciador de janelas xmonad para rastrear qual janela foi focada.

Surpreendentemente, você pode derivá-las aplicando técnicas de cálculo ao tipo da estrutura de dados original!

Aqui estão alguns:

• Sufixo tenta. Útil para quase todos os tipos de pesquisa de string (http://en.wikipedia.org/wiki/Suffix_trie#Functionality ). Veja também matrizes de sufixo; eles não são tão rápidos quanto árvores de sufixo, mas muito menores.

• Espalhe as árvores (como mencionado acima). A razão pela qual eles são legais é triplo:

  • Eles são pequenos: você só precisa dos ponteiros esquerdo e direito, como em qualquer árvore binária (nenhuma informação de cor ou tamanho do nó precisa ser armazenada)
  • Eles são (comparativamente) muito fáceis de implementar
  • Eles oferecem complexidade amortizada ideal para toda uma série de "critérios de medição" (o tempo de pesquisa é o que todos sabem). Vejohttp://en.wikipedia.org/wiki/Splay_tree#Performance_theorems

• Árvores de pesquisa ordenadas por heap: você armazena vários pares (chave, prio) em uma árvore, de modo que seja uma árvore de pesquisa em relação às chaves e ordenada por heap em relação às prioridades. Pode-se mostrar que essa árvore tem uma forma única (e nem sempre é totalmente empacotada para a esquerda). Com prioridades aleatórias, fornece o tempo esperado de pesquisa de O (log n), IIRC.

• Um nicho é a lista de adjacências para gráficos planares não direcionados com O (1) consultas de vizinhos. Essa não é uma estrutura de dados, mas uma maneira específica de organizar uma estrutura de dados existente. Aqui está como você faz isso: todo gráfico plano tem um nó com no máximo 6. Escolha um nó, coloque seus vizinhos na lista de vizinhos, remova-o do gráfico e recorra até que o gráfico esteja vazio. Quando receber um par (u, v), procure u na lista de vizinhos de v e na lista de vizinhos de v. Ambos têm tamanho no máximo 6, então é O (1).

Pelo algoritmo acima, se u e v forem vizinhos, você não terá u na lista de v e na lista de u. Se você precisar disso, basta adicionar os vizinhos ausentes de cada nó à lista de vizinhos desse nó, mas armazene quanto da lista de vizinhos você precisa procurar rapidamente.

Eu acho que as alternativas livres de bloqueio às estruturas de dados padrão, ou seja, fila, pilha e lista sem bloqueio, são muito negligenciadas.
Eles são cada vez mais relevantes, pois a concorrência se torna uma prioridade mais alta e é um objetivo muito mais admirável do que usar Mutexes ou bloqueios para lidar com leitura / gravação simultânea.

Aqui estão alguns links
http://www.cl.cam.ac.uk/research/srg/netos/lock-free/
http://www.research.ibm.com/people/m/michael/podc-1996.pdf [Links para PDF]
http://www.boyet.com/Articles/LockfreeStack.html

O blog de Mike Acton (muitas vezes provocador) tem excelentes artigos sobre design e abordagens sem bloqueio

Acho que Disjoint Set é bastante bacana para os casos em que você precisa dividir um monte de itens em conjuntos distintos e associar a consulta. A boa implementação das operações Union e Find resulta em custos amortizados efetivamente constantes (inverso da Função de Ackermnan, se bem me lembro da classe de estruturas de dados).

Montes de Fibonacci

Eles são usados ​​em alguns dos algoritmos mais rápidos conhecidos (assintoticamente) para muitos problemas relacionados a gráficos, como o problema de Caminho Mais Curto. O algoritmo de Dijkstra é executado no tempo O (E log V) com pilhas binárias padrão; o uso de pilhas de Fibonacci melhora isso para O (E + V log V), que é uma enorme aceleração para gráficos densos. Infelizmente, porém, eles têm um alto fator constante, tornando-os impraticáveis ​​na prática.

Qualquer pessoa com experiência em renderização em 3D deve estar familiarizada com as árvores BSP . Geralmente, é o método estruturando uma cena 3D para ser gerenciável para renderização, sabendo as coordenadas e o rumo da câmera.

O particionamento de espaço binário (BSP) é um método para subdividir recursivamente um espaço em conjuntos convexos por hiperplanos. Essa subdivisão dá origem a uma representação da cena por meio de uma estrutura de dados em árvore conhecida como árvore BSP.

Em outras palavras, é um método de dividir polígonos de forma complexa em conjuntos convexos ou polígonos menores, consistindo inteiramente de ângulos não reflexos (ângulos menores que 180 °). Para uma descrição mais geral do particionamento de espaço, consulte Particionamento de Espaço.

Originalmente, essa abordagem foi proposta em computação gráfica em 3D para aumentar a eficiência da renderização. Algumas outras aplicações incluem a execução de operações geométricas com formas (geometria sólida construtiva) em CAD, detecção de colisão em robótica e jogos de computador em 3D e outros aplicativos que envolvem o manuseio de cenas espaciais complexas.

Árvores Huffman - usadas para compactação.

Dê uma olhada no Finger Trees , especialmente se você é um fã das estruturas de dados puramente funcionais mencionadas anteriormente . Eles são uma representação funcional de sequências persistentes que dão suporte ao acesso aos fins em tempo constante amortizado e concatenação e divisão logarítmica no tempo no tamanho da peça menor.

Conforme artigo original :

Nossas árvores funcionais de 2-3 dedos são um exemplo de uma técnica geral de projeto introduzida por Okasaki (1998), chamada desaceleração recursiva implícita . Já observamos que essas árvores são uma extensão de sua estrutura implícita de deque, substituindo pares por 2-3 nós para fornecer a flexibilidade necessária para concatenação e divisão eficientes.

Uma Árvore dos Dedos pode ser parametrizada com um monóide , e o uso de diferentes monoides resultará em comportamentos diferentes para a árvore. Isso permite que as Finger Trees simulem outras estruturas de dados.

Buffer circular ou em anel - usado para streaming, entre outras coisas.

Estou surpreso que ninguém tenha mencionado as árvores Merkle (ou seja, Hash Trees ).

Utilizado em muitos casos (programas P2P, assinaturas digitais) em que você deseja verificar o hash de um arquivo inteiro quando tiver apenas parte do arquivo disponível.

Árvores <zvrba> Van Emde-Boas

Eu acho que seria útil saber por que eles são legais. Em geral, a pergunta "por que" é a mais importante a ser feita;)

Minha resposta é que eles fornecem dicionários O (log log n) com as teclas {1..n}, independentemente de quantas delas estão em uso. Assim como metade repetida fornece O (log n), sqrting repetido fornece O (log log n), que é o que acontece na árvore do vEB.

E as árvores espalhadas ?

Além disso, as estruturas de dados puramente funcionais de Chris Okasaki vêm à mente.

Uma variante interessante da tabela de hash é chamada Cuckoo Hashing . Ele usa várias funções de hash em vez de apenas 1 para lidar com colisões de hash. As colisões são resolvidas removendo o objeto antigo do local especificado pelo hash primário e movendo-o para um local especificado por uma função de hash alternativa. O Cuckoo Hashing permite um uso mais eficiente do espaço na memória, porque você pode aumentar seu fator de carga em até 91% com apenas 3 funções de hash e ainda ter um bom tempo de acesso.

Um heap min-max é uma variação de um heap que implementa uma fila de prioridade com extremidade dupla. Isso é alcançado com uma simples alteração na propriedade heap: uma árvore é dita como ordem min-max se todos os elementos nos níveis pares (ímpares) forem menores (maiores) do que todas as crianças e netos. Os níveis são numerados a partir de 1.

http://internet512.chonbuk.ac.kr/datastructure/heap/img/heap8.jpg

Eu gosto de estruturas de dados alheias ao cache . A idéia básica é colocar uma árvore em blocos recursivamente menores, para que caches de tamanhos diferentes aproveitem os blocos que cabem neles. Isso leva ao uso eficiente de armazenamento em cache em tudo, desde o cache L1 na RAM até grandes pedaços de dados lidos no disco sem precisar conhecer as especificidades dos tamanhos de qualquer uma dessas camadas de armazenamento em cache.

Esquerda, inclinando-se árvores vermelho-pretas . Uma implementação significativamente simplificada de árvores vermelho-pretas por Robert Sedgewick publicada em 2008 (~ metade das linhas de código a serem implementadas). Se você já teve problemas para entender a implementação de uma árvore Vermelho-Preto, leia sobre essa variante.

Muito semelhante (se não idêntico) ao Andersson Trees.

Fila de roubo de trabalho

Estrutura de dados sem bloqueio para dividir a igualdade de trabalho entre vários threads Implementação de uma fila de roubo de trabalho em C / C ++?

Bootstrap montões de inclinação-binomial por Gerth Stølting Brodal e Chris Okasaki:

Apesar do nome longo, eles fornecem operações de heap assintoticamente ideais, mesmo em uma configuração de função.

• O(1)tamanho, união , inserção, mínimo
• O(log n) deleteMin

Observe que a união leva, O(1)ao invés de O(log n)tempo, ao contrário dos heaps mais conhecidos que são comumente abordados nos manuais de estrutura de dados, como os de esquerda . E, ao contrário dos montes de Fibonacci , esses assintóticos são os piores casos, em vez de amortizados, mesmo se usados ​​persistentemente!

Existem várias implementações no Haskell.

Eles foram derivados em conjunto por Brodal e Okasaki, depois que Brodal criou uma pilha imperativa com os mesmos assintóticos.

• Kd-Trees , estrutura de dados espaciais usada (entre outros) no Raytracing em tempo real, tem a desvantagem de que os triângulos que se cruzam cruzam os diferentes espaços precisam ser cortados. Geralmente os BVHs são mais rápidos porque são mais leves.
• Os Quad-MX MX-CIF armazenam caixas delimitadoras em vez de conjuntos de pontos arbitrários, combinando uma quadtree comum com uma árvore binária nas bordas dos quads.
• HAMT , mapa de hash hierárquico com tempos de acesso que geralmente excedem O (1) hash-maps devido às constantes envolvidas.
• Índice invertido , bastante conhecido nos círculos dos mecanismos de pesquisa, porque é usado para recuperação rápida de documentos associados a diferentes termos de pesquisa.

Muitos, se não todos, estão documentados no Dicionário NIST de Algoritmos e Estruturas de Dados

Árvores de bola. Só porque eles fazem as pessoas rirem.

Uma árvore de bola é uma estrutura de dados que indexa pontos em um espaço métrico. Aqui está um artigo sobre como construí-los. Eles são freqüentemente usados ​​para encontrar vizinhos mais próximos de um ponto ou acelerar o k-means.

Não é realmente uma estrutura de dados; É mais uma maneira de otimizar matrizes alocadas dinamicamente, mas os buffers de lacunas usados ​​no Emacs são bem legais.

Árvore de Fenwick. É uma estrutura de dados para manter a contagem da soma de todos os elementos em um vetor, entre dois subíndices iej. A solução trivial, pré-calcular a soma desde o início, não permite atualizar um item (você precisa fazer O (n) trabalho para acompanhar).

As árvores Fenwick permitem atualizar e consultar em O (log n), e como ele funciona é muito legal e simples. É realmente bem explicado no artigo original de Fenwick, disponível gratuitamente aqui:

http://www.cs.ubc.ca/local/reading/proceedings/spe91-95/spe/vol24/issue3/spe884.pdf

Seu pai, a árvore RQM, também é muito legal: permite manter informações sobre o elemento mínimo entre dois índices do vetor e também funciona na atualização e consulta de O (log n). Eu gosto de ensinar primeiro o RQM e depois a Fenwick Tree.

Árvores Van Emde-Boas . Eu tenho até uma implementação em C ++ , para até 2 ^ 20 números inteiros.

Conjuntos aninhados são bons para representar árvores nos bancos de dados relacionais e executar consultas neles. Por exemplo, o ActiveRecord (ORM padrão do Ruby on Rails) vem com um plug-in de conjunto aninhado muito simples , que torna o trabalho com árvores trivial.

É bastante específico do domínio, mas a estrutura de dados de meia borda é bem organizada. Ele fornece uma maneira de iterar sobre malhas poligonais (faces e arestas), o que é muito útil em gráficos de computador e geometria computacional.