代码之家 › 专栏 › 技术社区 › Rob Lachlan

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

persistent functional-programming data-structures serialization language-agnostic

2

Rob Lachlan · 技术社区 · 16 年前

持久的数据结构依赖于结构的共享以提高效率。例如,请参见 here .

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

2 回复 | 直到 16 年前

1

6

Norman Ramsey 16 年前

你需要某种形式的散列考虑。这个问题研究得很好。安德鲁·肯尼迪的 paper on pickler combinators 详细说明如何在保留共享的同时序列化和取消序列化。

2

4

swestrup 16 年前

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

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

在这些选项之间进行选择取决于您试图优化的对象以及您希望在实践中看到的链接类型。