Onde posso encontrar informações sobre estruturas de dados usadas em software comum?

6

Como parte de um curso que estou ministrando sobre Estruturas de Dados, quero que os alunos pesquisem e apresentem o uso de Estruturas de Dados em softwares / serviços populares. No entanto, o Google básico mostra que essas informações não estão tão prontamente disponíveis.

Alguém pode me indicar os recursos certos que posso compartilhar com os alunos como ponto de partida para suas pesquisas?

EDITAR

A julgar pelas respostas recebidas, a pergunta original não é suficientemente clara, por isso estou adicionando mais detalhes.

Estou procurando recursos do tipo que afirmam, por exemplo, que o serviço-x usa a estrutura de dados-a para executar a funcionalidade-y por causa da propriedade-b . Este é o caso ideal. Outros recursos que fornecem informações semelhantes também são bem-vindos.

wsaleem
fonte
11
Com tantos softwares de código aberto e hospedados no GitHub, você pode tentar procurar por alguma estrutura de dados comumente usada no GitHub. Você encontrará um número incrível de hits por lá.
Andrew Au
Uma pesquisa como essa produz apenas implementações diretas da estrutura de dados, por exemplo, aqui . Estou procurando casos em que a estrutura de dados faz parte de um software maior. Talvez você possa sugerir uma maneira mais útil de pesquisar.
Wsaleem
Escolha seu livro favorito de estruturas e algoritmos de dados. Cada uma das estruturas descritas é usada com bastante frequência. E o mesmo acontece com estruturas mais exóticas (a literatura é exuberante), usadas nos casos em que o desempenho de seus irmãos monótonos fica aquém.
vonbrand
11
Escolha qualquer biblioteca de código aberto - existem muitas. Os alunos podem aprender muito pesquisando o código-fonte e a documentação, eu acho.
Raphael
2
@SamM Talvez não seja um "software popular", mas as pilhas de Fibonacci são frequentemente usadas na montagem de genoma e transcriptoma para sequenciamento de segunda geração. Montadores de novo, como Velvet e SOAPdenovo, usam o algoritmo de caminhos mais curtos de Dijkstra para detectar possíveis erros de leitura.
Pseudônimo

Respostas:

10

Em cima da minha cabeça:

Todo sistema operacional moderno usa árvores de pesquisa binária balanceadas para implementar o mapa de memória virtual de um processo. O Windows usa árvores splay, Linux e OS X usam árvores vermelho-pretas e o Solaris usa árvores AVL. Eles fazem isso porque o sistema operacional precisa armazenar o mapa de memória virtual em ordem (por endereço virtual), para permitir inserção e remoção rápidas e procurar regiões não utilizadas nas quais poderia alocar espaço.

Muitos jogos 3D modernos (por exemplo, qualquer coisa que use uma versão recente do Unreal Engine) usam octrees para determinar quais objetos são visíveis para a câmera. Eles fazem isso porque é bastante eficiente calcular quais nós se sobrepõem ao perfil de visualização de uma câmera.

Muitos roteadores (se não a maioria) usam árvores de raiz para implementar tabelas de roteamento. Eles fazem isso porque geralmente é o prefixo de um endereço de rede (ou seja, os bits mais significativos) que é importante, não a chave inteira. Além disso, a pesquisa leva tempo, que depende apenas do tamanho do endereço, não do número de entradas da tabela de roteamento, o que facilita a previsão do tempo.

As tabelas de hash são, é claro, usadas em qualquer lugar. O software antivírus o utiliza para realizar pesquisas em seu banco de dados de malware conhecido, os processadores de texto o utilizam para realizar verificações ortográficas, etc.

As estruturas de dados de gráficos são usadas por planilhas para implementar a avaliação. Pense em cada célula ocupada como um nó e desenhe um arco entre as células se o valor de uma depender diretamente do valor da outra. Quando uma entrada é alterada em uma célula, o gráfico é percorrido para determinar quais células precisam ser atualizadas com base nessa alteração.

Pseudônimo
fonte