Полностью постоянный связанный список
Почему нет какой-либо реализации (в C, C++, Java или даже Python...) полностью постоянного (не обязательно функционального) связанного списка, который имеет постоянные накладные расходы времени / пространства в количестве модификаций?
Я имею в виду структуру данных, описанную в этой статье: http://www.cs.cmu.edu/~sleator/papers/Persistence.htm
После долгого поиска в Google я не смог найти даже частично постоянную реализацию связанного списка с указанными выше издержками.
PS: определения постоянства, о которых я говорю, описаны на следующей странице Википедии: http://en.wikipedia.org/wiki/Persistent_data_structure
РЕДАКТИРОВАТЬ (после того, как вопрос был отложен):
Я не думаю, что упомянутая причина относится к моему вопросу. Я точно не прошу рекомендации между различными доступными библиотеками, поэтому не может быть "взвешенных ответов и спама". Мой вопрос вызывает удивление, что структура данных, которая должна быть великолепной в теории, не была реализована ни одним из известных языков. Поэтому, прежде чем я сам это реализовал, я задал этот вопрос, чтобы посмотреть, есть ли ответ типа: "Это нормально, структура данных X доминирует над той, которую вы ищете, и поэтому она не была реализована, несмотря на ее простоту". Другим ответом может быть: "Это не так хорошо, как вы думаете, поскольку существует большая скрытая константа" или "это не очень хорошо с тем, как в настоящее время создаются кэши"... Извините, если мой вопрос не был достаточно ясен. Я изменил свой вопрос, сделав мой запрос более четким сейчас.
1 ответ
Вы пробовали функциональную библиотеку Java? Он получил несколько постоянных структур данных: