Estruturas de dados persistentes/funcionais serializando

Question

As estruturas de dados persistentes dependem do compartilhamento da estrutura para obter eficiência. Por exemplo, veja aqui.

Como posso preservar o compartilhamento da estrutura quando serializo as estruturas de dados e as escrevo em um arquivo ou banco de dados? Se eu apenas atravessar ingenuamente as dados de dados, armazenarei os valores corretos, mas perderei o compartilhamento da estrutura. Eu gostaria de poder salvar estruturas de dados com componentes compartilhados em um arquivo, restaurá-los e ainda ter a maior parte da estrutura compartilhada nos dados restaurados.

Answer 1

Você quer algum tipo de consumo de hash. Esse problema foi bem estudado. Andrew Kennedy's Papel sobre combinadores de picadores Explica em detalhes como serializar e não -traduzir ao preservar o compartilhamento.

Answer 2

Existem dois métodos óbvios em que consigo pensar e eles estão relacionados.

1. Não serialize o estruturas, serialize o nós. Portanto, você armazenaria um registro serializado para cada um dos nós na árvore de exemplo que você deu e converteria todas as referências de nó em um nome de chave de banco de dados para o nó. Isso fornece compartilhamento automaticamente, mas tem o custo de ter que fazer várias pesquisas perseguindo as referências para carregar uma estrutura.
2. Colorir seus nós por propriedade, como no seu exemplo. Tenha um conceito de qual estrutura um determinado nó 'pertence' e apenas serialize os nós em uma estrutura que pertence a essa estrutura. Os links para nós em outras estruturas são substituídos por uma referência a essa estrutura e o nó em questão. Isso permite que você carregue uma estrutura inteira de uma só vez, mas pode fazer com que você precise carregar todas as estruturas relacionadas se elas estiverem altamente interligadas.

A escolha entre essas opções depende do que você está tentando otimizar e de que tipo de ligação você espera ver na prática.