Вопрос по – постоянная и неизменная структура данных

16

Есть ли разница в постоянной и неизменной структуре данных? Википедия относится к неизменной структуре данных при обсуждении постоянства, но у меня есть ощущение, что между ними может быть тонкая разница.

Ваш Ответ

2   ответа
21

это техника реализации. Среди прочего, это обеспечиваетpersistence, который является интерфейсом. API постоянства выглядит примерно так:

version update(operation o, version v) performs operation o on version v, returning a new version. If the data structure is immutable, the new version is a new structure (that may share immutable parts of the old structure). If the data structure isn't immutable, the returned version might just be a version number. The version v remains a valid version, and it shouldn't change in any observe-able way because of this update - the update is only visible in the returned version, not in v. data observe(query q, version v) observes a data structure at version v without changing it or creating a new version.

Подробнее об этих различиях см .:

The chapter "Persistent data structures" by Haim Kaplan in Handbook on Data Structures and Applications "Making Data Structures Persistent" by Driscoll et al. The first lecture of the Spring 2012 incarnation of MIT's 6.851: Advanced Data Structures
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
13

есть разница. Неизменяемая структура данных не может быть изменена каким-либо образом после ее создания. Единственный способ эффективно изменить его - это сделать изменчивую копию или что-то подобное (например, слегка изменив параметры, которые вы передаете конструктору нового). С другой стороны, постоянная структура данных является изменчивой в том смысле, что представленный API-интерфейс позволяет вносить изменения в структуру данных. В действительности, однако, любые изменения сохранят указатель на существующую структуру данных (и, следовательно, на каждую предыдущую структуру); кажется, они только изменяют структуру данных, потому что открытый API возвращает новый указатель, который может включать указатели на подмножество предыдущей структуры данных (например, в деревьях мы будем указывать на узел, поддерево которого не изменилось в результате операция).

Похожие вопросы