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, trees binárias e hashes, mas o que acontece com listas de Ignorar e filtros Bloom, por exemplo. Eu gostaria de saber mais estruturas de dados que não são tão comuns, mas valem a pena conhecer, porque elas contam com grandes ideias e enriquecem a checkbox de ferramentas de um programador.

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

EDIT : Por favor, tente include links para páginas descrevendo 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 cheguem ao topo com base apenas em seus votos.

Tentativas , também conhecidas como trees de prefixos ou trees críticas , existem há mais de 40 anos, mas ainda são relativamente desconhecidas. Um uso muito legal de tentativas é descrito em ” TRASH – Uma estrutura dinâmica de dados LC-trie e hash “, que combina um trie com uma function hash.

Bloom filter : matriz de bits de m bits, inicialmente todos configurados para 0.

Para adicionar um item, você o executa através de funções hash que lhe dão k índices na matriz que você define como 1.

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

Claro, isso dá alguma probabilidade de falsos positivos (de acordo com a wikipedia é sobre 0,61 ^ (m / n) onde 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 a contagem do filtro de bloom , representado por uma matriz de ints e incremento / decremento.

Corda : É uma string que permite inserções, substrings, inserções intermediárias e anexos baratos. Eu realmente só usei uma vez, mas nenhuma outra estrutura teria sido suficiente. As sequências regulares de sequências e arrays eram muito caras para o que precisávamos fazer, e reverter tudo estava fora de questão.

As listas de skip são bem legais.

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

Eles podem ser usados ​​como uma alternativa para trees balanceadas (usando balanceamento probabilístico em vez de aplicação estrita de balanceamento). Eles são fáceis de implementar e mais rápidos do que dizer, uma tree vermelha e preta. Eu acho que eles deveriam estar em todos os bons programadores.

Se você deseja obter uma introdução aprofundada para as 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 Faixas.

Índices espaciais , em particular trees R e trees KD , armazenam dados espaciais de forma eficiente. Eles são bons para dados de coordenadas de mapas geocharts e algoritmos de localização e rota de VLSI e, às vezes, para pesquisa de vizinhos mais próximos.

Bit Arrays armazenam bits individuais de forma compacta e permitem operações de bits rápidas.

Zíperes – derivados de estruturas de dados que modificam a estrutura para ter uma noção natural de ‘cursor’ – localização atual. Eles são realmente úteis, pois garantem que os índices não podem estar fora do limite – usados, por exemplo, no gerenciador de janelas xmonad para rastrear qual janela está focada.

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

Aqui estão alguns:

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

  • Splay trees (como mencionado acima). A razão pela qual eles são legais é tripla:

    • Eles são pequenos: você só precisa dos pointers da esquerda e da direita, como você faz em qualquer tree 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 uma complexidade amortizada ideal para toda uma série de “critérios de medição” (o tempo de pesquisa log n é aquele que todos conhecem). Veja http://en.wikipedia.org/wiki/Splay_tree#Performance_theorems
  • Árvores de pesquisa ordenadas por heap: você armazena vários pares (chave, prio) em uma tree, de modo que seja uma tree de busca em relação às chaves e ordenada por heap em relação às prioridades. Pode-se mostrar que essa tree tem uma forma única (e nem sempre é totalmente empacotada para cima e para a esquerda). Com prioridades aleatórias, você recebe o tempo de pesquisa O (log n) esperado, IIRC.

  • Um nicho é uma lista de adjacências para grafos planares não direcionados com consultas vizinhas O (1). Isso não é tanto uma estrutura de dados como uma maneira particular de organizar uma estrutura de dados existente. Veja como você faz isso: todo grafo planar tem um nó com grau no máximo 6. Escolha um desses nós, coloque seus vizinhos em sua lista vizinha, remova-os do gráfico e recurse até que o gráfico esteja vazio. Quando dado um par (u, v), procure por u na lista de vizinhos de v e por v na lista de vizinhos de v. Ambos têm tamanho máximo de 6, então este é O (1).

Pelo algoritmo acima, se u e v forem vizinhos, você não terá a lista u in v e a lista v in u. Se você precisar disso, apenas adicione os vizinhos ausentes de cada nó à lista de vizinhos desse nó, mas armazene quanto da lista de vizinhos você precisa procurar para uma consulta rápida.

Eu acho que alternativas livres de bloqueio para estruturas de dados padrão ou seja, fila livre de bloqueio, pilha e lista são muito negligenciadas.
Eles são cada vez mais relevantes à medida que a simultaneidade se torna uma prioridade mais alta e são um objective muito mais admirável do que o uso de Mutexes ou bloqueios para lidar com leituras / gravações simultâneas.

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 provocativo) tem alguns artigos excelentes sobre design e abordagens livres de bloqueio

Eu acho que Disjoint Set é muito bacana para casos em que você precisa dividir um monte de itens em conjuntos distintos e consultar a associação. A boa implementação das operações Union e Find resulta em custos amortizados que são efetivamente constantes (inverso da function de Ackerman, se eu me lembro corretamente da minha class de estruturas de dados).

Pilhas de Fibonacci

Eles são usados ​​em alguns dos algoritmos mais rápidos conhecidos (assintoticamente) para muitos problemas relacionados a charts, como o problema do caminho mais curto. O algoritmo de Dijkstra é executado no tempo O (E log V) com heaps binários padrão; O uso de heaps de Fibonacci melhora isso para O (E + V log V), que é um enorme aumento de velocidade para charts densos. Infelizmente, porém, eles têm um fator constante elevado, muitas vezes tornando-os impraticáveis ​​na prática.

Qualquer pessoa com experiência em renderização 3D deve estar familiarizada com as trees BSP . Geralmente, é o método de estruturar uma cena 3D para ser gerenciável para renderizar o conhecimento das coordenadas e do rolamento 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. Esta subdivisão dá origem a uma representação da cena por meio de uma estrutura de dados em tree conhecida como tree BSP.

Em outras palavras, é um método de quebrar polígonos com formas complexas em conjuntos convexos, ou polígonos menores consistindo inteiramente de ângulos não reflexos (ângulos menores que 180 °). Para obter 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 3D para aumentar a eficiência da renderização. Algumas outras aplicações incluem a execução de operações geométricas com formas (geometry sólida construtiva) em CAD, detecção de colisão em jogos de computador robóticos e 3D, e outras aplicações de computador que envolvem o manuseio de cenas espaciais complexas.

Árvores Huffman – usadas para compression.

Dê uma olhada nos Finger Trees , especialmente se você for fã das estruturas de dados puramente funcionais mencionadas anteriormente . Eles são uma representação funcional de sequências persistentes que suportam o access às extremidades em tempo constante amortizado e concatenação e divisão no tempo logarítmico no tamanho da peça menor.

Conforme o artigo original :

Nossas trees funcionais de 2 a 3 dedos são uma instância de uma técnica de projeto geral introduzida por Okasaki (1998), chamada de desaceleração recursiva implícita . Já observamos que essas trees são uma extensão de sua estrutura implícita de deques, substituindo os pares por dois ou três nós para fornecer a flexibilidade necessária para uma concatenação e divisão eficiente.

Uma tree de dedo pode ser parametrizada com um monóide e usar diferentes monoides resultará em diferentes comportamentos para a tree. Isso permite que o Finger Trees simule outras estruturas de dados.

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

Estou surpreso que ninguém mencionou trees Merkle (ie. Hash Trees ).

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

Árvores 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 perguntar;)

Minha resposta é que eles dão a você dictionarys O (log log n) com {1..n} chaves, independente de quantas chaves estão em uso. Assim como a divisão repetida da metade dá a você O (log n), o sqrting repetido dá a você O (log log n), que é o que acontece na tree vEB.

Como cerca de trees splay ?

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

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

Um heap min-max é uma variação de um heap que implementa uma fila de prioridade de finalização dupla. Isso é conseguido por meio de uma simples mudança na propriedade heap: Uma tree é dita como max-max ordenada se cada elemento em níveis pares (ímpares) for menor (maior) que todos os filhos e netos. Os níveis são numerados a partir de 1.

http://sofpt.miximages.com/data-structures/heap8.jpg

Eu gosto de dados do Cache Oblivious . A idéia básica é criar uma tree em blocos recursivamente menores, de forma que os caches de muitos tamanhos diferentes aproveitem blocos que se encheckboxm perfeitamente neles. Isso leva ao uso eficiente do cache em tudo, desde o cache L1 na RAM até grandes blocos de dados lidos do disco sem a necessidade de conhecer as especificidades dos tamanhos de qualquer uma dessas camadas de cache.

Árvores inclinando-se à esquerda vermelho-preto . Uma implementação significativamente simplificada de trees vermelhas e pretas por Robert Sedgewick, publicada em 2008 (~ metade das linhas de código a serem implementadas). Se você já teve problemas para resolver a implementação de uma tree vermelha e preta, leia sobre essa variante.

Muito similar (se não idêntico) a Andersson Trees.

Fila de roubo de trabalho

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

Bootstrapped skew-binomial heaps por Gerth Stølting Brodal e Chris Okasaki:

Apesar de seu nome longo, eles fornecem operações de heap otimizadas assintoticamente, mesmo em uma configuração de function.

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

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

Existem várias implementações no Haskell.

Eles foram conjuntamente derivados por Brodal e Okasaki, depois que Brodal surgiu com 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 cruzam os diferentes espaços precisam ser cortados. Geralmente os BVH são mais rápidos porque são mais leves.
  • MX-CIF Quadtrees , armazena checkboxs delimitadoras em vez de conjuntos de pontos arbitrários, combinando uma quadtree regular com uma tree binária nas bordas dos quadriciclos.
  • HAMT , mapa hash hierárquico com tempos de access que geralmente excedem os mapas hash O (1) devido às constantes envolvidas.
  • Índice invertido , bastante conhecido nos círculos do mecanismo de pesquisa, porque é usado para recuperação rápida de documentos associados a diferentes termos de pesquisa.

A maioria desses documentos, se não todos, está documentada no Dicionário NIST de Algoritmos e Estruturas de Dados.

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

Uma tree de bolas é 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 a um ponto ou acelerar k-médias.

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

Fenwick Tree. É uma estrutura de dados para manter a contagem da sum de todos os elementos em um vetor, entre dois subindices indicados i e j. A solução trivial, precalculando a sum desde o começo não permite atualizar um item (você tem que fazer O (n) trabalhar para manter-se).

As trees Fenwick permitem que você atualize e consulte em O (log n), e como isso funciona é muito legal e simples. É muito 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 tree RQM também é muito legal: Ele permite que você mantenha informações sobre o elemento mínimo entre dois índices do vetor, e também funciona na atualização e consulta O (log n). Eu gosto de ensinar primeiro o RQM e depois a Fenwick Tree.

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

Conjuntos nesteds são bons para representar trees nos bancos de dados relacionais e executar consultas neles. Por exemplo, o ActiveRecord (ORM padrão do Ruby on Rails) vem com um plugin de conjunto nested muito simples, o que torna o trabalho com trees trivial.

É bastante específico de domínio, mas a estrutura de dados de meia-borda é bem legal. Ele fornece uma maneira de iterar em malhas de polígonos (faces e arestas) que é muito útil em computação gráfica e geometry computacional.