序列化持久性/功能性数据结构

Question

持久性数据结构取决于共享结构以提高效率。有关示例，请参阅here。

当我序列化数据结构并将它们写入文件或数据库时，如何保持结构共享？如果我只是天真地遍历数据结构，我会存储正确的值，但是我将失去结构共享。我希望能够将具有共享组件的数据结构保存到文件中，恢复它们，并且仍然可以在恢复的数据中共享大部分结构。

Answer 1

你想要某种形式的散列表。这个问题已经得到很好的研究。 Andrew Kennedy的paper on pickler combinators详细解释了如何序列化和反序列化，同时保持共享。

Answer 2

我可以想到两种明显的方法，它们是相关的。

1. 不要序列的结构，序列化节点。因此，您需要为所给示例树中的每个节点存储序列化记录，并且将所有节点引用都转换为该节点的数据库键名称。这样可以自动分享，但是为了加载结构，必须执行多个追查引用的代价。
2. 按照所有权为节点着色，就像你的例子。有一个给定节点“属于”哪一个结构的概念，并且仅对该结构中属于该结构的结构进行序列化。链接到其他结构中的节点的链接被对该结构和所讨论的节点的引用所取代。这允许您一次加载整个结构，但如果它们高度相互关联，则可能导致您必须加载所有相关结构。

这些选项之间进行选择取决于你想怎么优化，以及你期望在实践中看到什么类型联动。