Сериализация устойчивых/функциональных структур данных

Question

Стойкие структуры данных зависят от совместного использования структуры для эффективности. Например, см. here.

Как я могу сохранить совместное использование структуры, когда я сериализую структуры данных и записываю их в файл или базу данных? Если я просто наивно перехожу к структурам данных, я сохраню правильные значения, но я потеряю совместное использование структуры. Я хотел бы иметь возможность сохранять структуры данных с общими компонентами в файл, восстанавливать их и по-прежнему иметь большую часть структуры, совместно используемой в восстановленных данных.

Answer 1

Вам нужна какая-то форма хэш-consing. Эта проблема хорошо изучена. Эндрю Кеннеди paper on pickler combinators подробно объясняет, как сериализовать и неэтериализовать, сохраняя совместное использование.

Answer 2

Есть два очевидных метода, о которых я могу думать, и они связаны между собой.

1. Не сериализации структуры, сериализовать узлы. Таким образом, вы сохраните сериализованную запись для каждого из узлов в дереве примеров, которые вы указали, и вы конвертируете все ссылки на узлы в имя ключа базы данных для узла. Это дает вам общий доступ, но имеет стоимость необходимости выполнять несколько поисковых запросов, преследуя ссылки, чтобы загрузить структуру.
2. Цвет ваших узлов по собственному усмотрению, как в вашем примере. Имейте понятие о том, какая структура данного узла «принадлежит» и только сериализует узлы в структуре, принадлежащей этой структуре. Ссылки на узлы в других структурах заменяются ссылкой на эту структуру и рассматриваемый узел. Это позволяет сразу загрузить всю структуру, но может привести к загрузке всех связанных структур, если они очень взаимосвязаны.

Выбор между этими параметрами зависит от того, что вы пытаетесь оптимизировать и какие виды связи вы ожидаете увидеть на практике.