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

Question

持久化数据结构依赖于结构共享来提高效率。例如，请参见此处。

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

Answer 1

你想要某种形式的哈希计算。这个问题已经被很好地研究过了。Andrew Kennedy关于pickler 组合器的论文详细解释了如何在保留共享的同时进行序列化和反序列化。

Answer 2

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

1. 不要序列化结构，序列化节点。因此，您将为您提供的示例树中的每个节点存储一个序列化记录，并将所有节点引用转换为该节点的数据库键名。这使您可以自动共享，但必须进行多次查找以跟踪引用以加载结构。
2. 按所有权为节点着色，如您的示例中所示。对给定节点“属于”哪个结构有一个概念，并且只序列化属于该结构的结构中的节点。到其他结构中的节点的链接被对该结构和相关节点的引用所取代。这允许您一次加载整个结构，但如果它们高度互连，则可能导致您必须加载所有相关结构。

在这些选项之间进行选择取决于您要优化什么，以及您希望在实践中看到什么样的链接。