序列化持久性/功能性數據結構

Question

持久性數據結構取決於共享結構以提高效率。有關示例，請參閱here。

當我序列化數據結構並將它們寫入文件或數據庫時，如何保持結構共享？如果我只是天真地遍歷數據結構，我會存儲正確的值，但是我將失去結構共享。我希望能夠將具有共享組件的數據結構保存到文件中，恢復它們，並且仍然可以在恢復的數據中共享大部分結構。

Answer 1

你想要某種形式的散列表。這個問題已經得到很好的研究。 Andrew Kennedy的paper on pickler combinators詳細解釋瞭如何序列化和反序列化，同時保持共享。

Answer 2

我可以想到兩種明顯的方法，它們是相關的。

1. 不要序列的結構，序列化節點。因此，您需要爲所給示例樹中的每個節點存儲序列化記錄，並且將所有節點引用都轉換爲該節點的數據庫鍵名稱。這樣可以自動分享，但是爲了加載結構，必須執行多個追查引用的代價。
2. 按照所有權爲節點着色，就像你的例子。有一個給定節點「屬於」哪一個結構的概念，並且僅對該結構中屬於該結構的結構進行序列化。鏈接到其他結構中的節點的鏈接被對該結構和所討論的節點的引用所取代。這允許您一次加載整個結構，但如果它們高度相互關聯，則可能導致您必須加載所有相關結構。

這些選項之間進行選擇取決於你想怎麼優化，以及你期望在實踐中看到什麼類型聯動。