language-agnostic - 永続的/機能的なデータ構造のシリアル化

Question

永続データ構造は、効率のために構造の共有に依存しています。例については、こちらをご覧ください。

データ構造をシリアル化してファイルまたはデータベースに書き込むときに、構造共有を保持するにはどうすればよいですか？データ構造を単純にトラバースすると、正しい値が格納されますが、構造の共有は失われます。共有コンポーネントを含むデータ構造をファイルに保存して復元し、復元されたデータでほとんどの構造を共有できるようにしたいと思います。

Answer 1

なんらかの形のハッシュコンシングが必要です。この問題はよく研究されています。ピッカーコンビネータに関するAndrewKennedyの論文では、共有を維持しながらシリアル化および非シリアル化する方法について詳しく説明しています。

Answer 2

私が考えることができる2つの明白な方法があり、それらは関連しています。

1. 構造をシリアル化せず、ノードをシリアル化します。したがって、指定したサンプルツリーの各ノードのシリアル化されたレコードを保存し、すべてのノード参照をノードのデータベースキー名に変換します。これにより、自動的に共有できますが、構造をロードするために参照を追跡する複数のルックアップを実行する必要があります。
2. 例のように、所有権によってノードに色を付けます。特定のノードが「属する」構造の概念を持ち、その構造に属する構造内のノードのみをシリアル化します。他の構造のノードへのリンクは、その構造と問題のノードへの参照に置き換えられます。これにより、構造全体を一度にロードできますが、高度に相互リンクされている場合は、関連するすべての構造をロードする必要が生じる可能性があります。

これらのオプションのどちらを選択するかは、最適化しようとしているものと、実際に見られると予想されるリンクの種類によって異なります。