Como escolho uma estrutura de dados do dicionário funcional?

10

Eu li um pouco sobre as seguintes estruturas de dados:

  • O Hash ideal de Bagwell tenta
  • Tabelas hash dinâmicas de Larson
  • Árvores vermelho-pretas
  • Patricia árvores

... e tenho certeza que existem muitos outros por aí. Eu tenho visto muito pouco sobre o que cada um é mais adequado, ou por que eu escolheria um sobre o outro. Então, aqui estão algumas perguntas nesse sentido:

  1. Quais estruturas de dados do dicionário funcional são importantes para se conhecer?
  2. Quais são os prós e os contras dessas abordagens?
  3. Quando faz sentido usar uma estrutura de dados mais imperativa?

Os números 2 e 3 são os mais importantes. :-)

Jason
fonte
Relacionado: O que há de novo em estruturas de dados puramente funcionais desde Okasaki? (Essa pergunta não se restringe a dicionários.) #
Tsuyoshi Ito
Esta questão (que não seja o item numerado 3) tem a sensação de uma [grande lista].
Kaveh
2
seria útil saber se a pergunta vinculada acima aborda suas preocupações e, se não, por que não?
Suresh Venkat
@Suresh - Isso responde # 1, mas 2 e 3 foram os mais importantes. Estou procurando principalmente uma visão geral para determinar quais valem a pena estudar com mais profundidade.
Jason
2
Está bem. então pode valer a pena editar a pergunta então.
Suresh Venkat

Respostas:

16

Na verdade, não consigo responder à segunda posição sem me perder (existem muitas dimensões pelas quais você pode comparar essas estruturas), mas para a terceira a resposta é bem simples.

Use uma estrutura de dados imperativa se: (a) não houver absolutamente nenhum alias ou (b) você realmente precisar usar o alias para uma transmissão eficiente.

Se não houver nenhum alias da sua estrutura de dados, você não estará aproveitando o fato de que as estruturas de dados funcionais são persistentes. Portanto, não há razão para pagar pelos custos. Existem duas advertências para esse conselho. Primeiro, você pode preferir a simplicidade da implementação de uma estrutura de dados funcional: implementar a exclusão de uma árvore vermelho-preta funcional o fará amaldiçoar, mas implementar a exclusão em uma árvore vermelha-preta imperativa com indicadores principais o deixará pensando em suicídio. Segundo, a atribuição pode ser mais cara do que o esperado em uma linguagem do Gc, pois as gravações podem fazer com que as estruturas de dados sejam removidas da geração jovem. Realmente não temos uma boa teoria sobre efeitos de cache e gc, então você não tem escolha a não ser fazer comparações.

Segundo, se você precisa de um canal de transmissão, uma estrutura de dados compartilhada é uma excelente maneira de fazer isso. Com uma atualização constante, você pode dizer arbitrariamente a muitas outras pessoas que um valor foi alterado. (É por isso que o union-find é uma estrutura de dados tão boa.) Com uma configuração puramente funcional, você precisa modificar todas as outras pessoas ou fornecer indicadores abstratos para um estado que você codifica manualmente (que é uma espécie de obtusa coisa para fazer).

Se você não quiser argumentar sobre alias e propriedade de objeto, ou se precisar de várias versões da mesma estrutura de dados (você precisa de uma versão nova e uma antiga, por exemplo), use apenas uma estrutura de dados funcional.

O lugar onde acho mais difícil seguir esses conselhos é com algoritmos de gráficos. Existem muitos algoritmos de gráfico imperativo realmente elegantes, mas geralmente é o caso (digamos, ao escrever compiladores) que você também deseja persistência. As pessoas geralmente tentam dividir a diferença e usar o algoritmo imperativo legal, mas tentam colocar versões para o lado para obter persistência. Isso geralmente é horrível, cheio de bugs e propenso a perder a vantagem de desempenho do algoritmo imperativo.

Neel Krishnaswami
fonte
2
o que é aliasing neste contexto?
Suresh Venkat
6
Alias ​​é quando você tem várias referências ao mesmo pedaço de dados. Se esses dados são mutáveis, o raciocínio sobre um programa que os utiliza deve levar em conta explicitamente todos os outros subprogramas que podem acessá-los e modificá-los. Se esse dado for imutável, você poderá argumentar localmente sobre um programa que o utilize, ignorando o alias, pois você sabe que ninguém que pode acessar os dados pode modificá-lo.
Neel Krishnaswami 1/1
"mas implementar a exclusão em uma árvore imprescindível vermelho-preto com indicadores dos pais deixará você pensando em suicídio" Confira as árvores preto-vermelho inclinadas à esquerda de Sedgewick. O caso geral de exclusão é reduzido para delete-min por um truque padrão, e o próprio delete-min é muito simples para as árvores LLRB. Nenhum ponteiro pai é necessário.
Por Vognsen
11
"Isso geralmente é horrível, cheio de bugs e propenso a perder a vantagem de desempenho do algoritmo imperativo". O artigo de Norman Ramsey sobre o uso de zíperes para gráficos de fluxo de controle em um compilador de otimização fornece um exemplo de compromisso convincente. Você possui efetivamente um heap local para oferecer suporte à religação fácil e eficiente de referências entre blocos básicos em um CFG, mas a manipulação do conteúdo de blocos básicos é funcional (ou semi-funcional, dependendo da visão filosófica dos zíperes).
Por Vognsen
1

Quais estruturas de dados do dicionário funcional são importantes para se conhecer?

Árvores binárias com altura equilibrada e suas tentativas são um bom compromisso geral. Além disso:

  • Patricia árvores.
  • Hash tenta.

Quais são os prós e os contras dessas abordagens?

Árvores binárias com altura equilibrada e suas tentativas são um bom compromisso geral para chaves atômicas. Tentativas são as mesmas para chaves que são sequências, por exemplo, chaves de sequência.

As árvores Patricia podem ser várias vezes mais rápidas, mas apenas permitem chaves inteiras.

As tentativas de hash podem ser várias vezes mais rápidas que as árvores binárias balanceadas, principalmente se o hash for mais barato que a comparação e o polimorfismo tiver uma sobrecarga (por exemplo, strings no .NET) e escrever ponteiros no heap for rápido (por exemplo, VMs como a JVM e CLR que foram otimizado para linguagens imperativas em vez de linguagens funcionais). As tentativas de hash também permitem o uso interno da mutação como uma otimização.

As árvores preto-vermelho são menos importantes porque não têm benefícios significativos em relação às árvores de altura equilibrada, mas têm a desvantagem significativa de não permitirem união, interseção e diferença eficientes.

Da mesma forma, as árvores de dedos não são muito melhores na prática.

Quando faz sentido usar uma estrutura de dados mais imperativa?

Quando o seu dicionário é preenchido uma vez e depois usado apenas para pesquisas, ou seja, congelado.

Quando você precisa de desempenho (uma tabela de hash decente como o .NET Dictionarygeralmente é 10-40 × mais rápida que qualquer dicionário genérico puramente funcional).

Quando você precisa de um dicionário fraco, porque não há um dicionário fraco puramente funcional conhecido.

Jon Harrop
fonte