Введение

Структура данных, которая всегда сохраняет предыдущую версию себя при изменении.

В информатике, персистентная структура данных или не-эфемерная структура данных – это структура данных, которая всегда сохраняет предыдущую версию себя при модификации. Такие структуры данных фактически неизменяемы, поскольку их операции не обновляют структуру на месте (видимо), а вместо этого всегда возвращают новую обновлённую структуру. Термин был введен в статье Дрисколла, Сарнака, Слейтора и Тарджана в 1986 году. Структура данных является частично персистентной, если доступ ко всем версиям возможен, но изменяется только самая новая версия. Структура данных является полностью персистентной, если к каждой версии можно получить доступ и её изменить. Если также существует операция объединения (meld или merge), которая может создать новую версию из двух предыдущих версий, структура данных называется конфлюентно-персистентной. Структуры, которые не являются персистентными, называются эфемерными. Эти типы структур данных особенно распространены в логическом и функциональном программировании. В полностью персистентной модели разрешены как обновления, так и запросы к любой версии структуры данных. В некоторых случаях производительность запросов или обновлений старых версий структуры данных может снижаться, как это происходит со структурой данных "веревка" (rope). Кроме того, структура данных может называться конфлюентно-персистентной, если, помимо полной персистентности, две версии одной и той же структуры данных могут быть объединены для создания новой версии, которая также остаётся полностью персистентной.

Частично постоянная структура данных

Тип структуры данных, в которой пользователь может запрашивать любую версию структуры, но обновлять только последнюю. Эфемерная структура данных может быть преобразована в частично-персистентную структуру данных, используя несколько техник. Одной из техник является использование рандомизированной версии дерева Ван Эмде Боаса, создаваемого с помощью динамического идеального хеширования. Эта структура данных создается следующим образом:

Стратифицированное дерево с m элементами реализуется с использованием динамического идеального хеширования. Дерево обрезается путем разделения m элементов на корзины размером log(log n) таким образом, что элементы первой корзины меньше элементов второй корзины и так далее. Максимальный элемент в каждой корзине хранится в стратифицированном дереве, а каждая корзина хранится в структуре как неупорядоченный связный список. Размер этой структуры данных ограничен числом элементов, хранящихся в структуре, то есть O(m). Вставка нового максимального элемента выполняется за константное O(1) ожидаемое и амортизированное время. Наконец, поиск элемента в этой структуре может быть выполнен за O(log(log n)) времени в худшем случае.

Копирование на письменном носителе

Один из способов создания персистентной структуры данных — использовать предоставляемую платформой временную структуру данных, такую как массив, для хранения данных в структуре и копировать всю эту структуру данных, используя семантику копирования при записи для любых изменений структуры данных. Это неэффективный подход, поскольку вся базовая структура данных должна быть скопирована при каждой записи, что приводит к наихудшей временной сложности O(n·m) для m модификаций массива размером n.

Жирный узел

Метод "жирных" узлов заключается в записи всех изменений, вносимых в поля узлов, непосредственно в самих узлах, без удаления старых значений полей. Это требует, чтобы узлы могли становиться сколь угодно "жирными". Иными словами, каждый "жирный" узел содержит ту же информацию и поля-указатели, что и эфемерный узел, а также место для произвольного количества дополнительных значений полей. Каждое дополнительное значение поля имеет соответствующее имя поля и метку версии, указывающую версию, в которой данное поле было изменено до указанного значения. Кроме того, каждый "жирный" узел имеет собственную метку версии, указывающую версию, в которой узел был создан. Единственная цель меток версии узлов – гарантировать, что каждый узел содержит только одно значение для каждого имени поля в каждой версии. Для навигации по структуре каждое исходное значение поля в узле имеет метку версии, равную нулю.

Сложность жирового узла

При использовании метода "жирного узла" требуется O(1) памяти для каждой модификации: достаточно сохранить новые данные. Каждая модификация занимает O(1) дополнительного времени на сохранение в конец истории модификаций. Это амортизированная оценка времени, предполагающая, что история модификаций хранится в динамически расширяемом массиве. Во время доступа необходимо найти правильную версию в каждом узле при обходе структуры. Если было выполнено "m" модификаций, то каждая операция доступа будет иметь замедление O(log m), обусловленное стоимостью поиска ближайшей модификации в массиве.

Копирование пути

При использовании метода копирования пути создается копия всех узлов на пути к любому узлу, который предстоит изменить. Затем эти изменения необходимо последовательно распространить по всей структуре данных: все узлы, указывавшие на старый узел, должны быть перенаправлены на новый узел. Эти перенаправления вызывают дальнейшие каскадные изменения, и так далее, пока не будет достигнут корневой узел.

Сложность копирования пути

При m модификациях это требует O(log m) времени на поиск с дополнением. Время и объем памяти, необходимые для модификации, ограничены длиной самого длинного пути в структуре данных и стоимостью обновления в эфемерной структуре данных. В сбалансированном двоичном дереве поиска без указателей на родительские узлы наихудшая временная сложность модификации составляет O(log n + стоимость обновления). Однако в связном списке наихудшая временная сложность модификации составляет O(n + стоимость обновления).

Сочетание

Дрисколл, Сарнак, Слейтор, Тарджан предложили стеки, кучи и треапы, которые легко адаптировать для создания персистентной версии. Некоторые другие структуры требуют немного больше усилий, например: очереди, двусторонние очереди и их расширения, включая мини-двусторонние очереди (которые имеют дополнительную операцию O(1) для нахождения минимального элемента) и двусторонние очереди с произвольным доступом (которые имеют дополнительную операцию произвольного доступа с суб-линейной, чаще всего логарифмической сложностью). Существуют также персистентные структуры данных, использующие деструктивные операции, что делает их неэффективными в чисто функциональных языках (например, Haskell вне специализированных монад, таких как state или IO), но реализуемыми в языках, таких как C или Java. Часто можно избежать использования таких структур данных, выбрав другую реализацию. Основное преимущество чисто персистентных структур данных заключается в их лучшей производительности в многопоточных средах.

Хаскелл

Хаскелл — это чисто функциональный язык и, следовательно, не допускает изменение состояния. Поэтому все структуры данных в этом языке являются персистентными, так как функциональная семантика не позволяет не сохранять предыдущее состояние структуры данных. Это обусловлено тем, что любое изменение структуры данных, которое привело бы к недействительности предыдущих версий, нарушило бы референциальную прозрачность. В стандартной библиотеке Haskell имеются эффективные персистентные реализации связных списков, отображений (реализованных как сбалансированные по размеру деревья) и множеств, среди прочего.

Замыкание

Как и многие языки программирования семейства Lisp, Clojure включает реализацию связного списка, но в отличие от других диалектов, в его реализации связного списка постоянство обеспечивается по умолчанию, а не является соглашением. Clojure также имеет эффективные реализации постоянных векторов, отображений и множеств, основанные на постоянных хеш-массивах, реализованных в виде деревьев поиска. Эти структуры данных реализуют обязательные, предназначенные только для чтения части Java Collections Framework. Разработчики языка Clojure рекомендуют использовать постоянные структуры данных вместо изменяемых, поскольку они обладают семантикой по значению, что дает преимущества в виде возможности свободного обмена ими между потоками с использованием дешевых псевдонимов, простоты создания и независимости от языка. Эти структуры данных лежат в основе поддержки параллельных вычислений в Clojure, поскольку они позволяют легко повторять операции для избежания гонок данных и обеспечивают атомарную семантику сравнения и обмена.

Ульма

Язык программирования Elm является чисто функциональным, как Haskell, что обуславливает неизменяемость всех его структур данных. Он включает в себя неизменяемые реализации связных списков, а также массивов, словарей и множеств. Elm использует собственную реализацию виртуального DOM, которая использует преимущества неизменяемости данных Elm. По состоянию на 2016 год разработчики Elm заявили, что благодаря этому виртуальному DOM язык Elm отрисовывает HTML быстрее, чем популярные JavaScript-фреймворки React, Ember и Angular.

Ява

Язык программирования Java не является особенно функциональным. Несмотря на это, основной пакет JDK – `java.util.concurrent` включает `CopyOnWriteArrayList` и `CopyOnWriteArraySet`, которые представляют собой персистентные структуры, реализованные с использованием техники копирования при записи. Однако, стандартная реализация конкурентной карты в Java, `ConcurrentHashMap`, не является персистентной. Полностью персистентные коллекции доступны в сторонних библиотеках или других языках JVM.

Язык JavaScript

Популярный JavaScript-фронтенд-фреймворк React часто используется вместе с системой управления состоянием, реализующей архитектуру Flux, одной из популярных реализаций которой является JavaScript-библиотека Redux. Библиотека Redux вдохновлена моделью управления состоянием, используемой в языке программирования Elm, что означает, что она предписывает пользователям рассматривать все данные как неизменяемые. В результате проект Redux рекомендует в некоторых случаях использовать библиотеки для обеспечения эффективных и устойчивых структур данных. Сообщается, что это позволяет достичь большей производительности, чем при сравнении или создании копий обычных объектов JavaScript. Одна из таких библиотек устойчивых структур данных – Immutable.js – основана на структурах данных, представленных и популяризированных Clojure и Scala. Она упоминается в документации Redux как одна из возможных библиотек, обеспечивающих принудительную неизменяемость. Immer.js предлагает интересный подход, при котором "следующее неизменяемое состояние создается путем мутации текущего". Immer.js использует нативные JavaScript-объекты, а не эффективные устойчивые структуры данных, что может привести к проблемам с производительностью при больших объемах данных.

Пролог

Термины Prolog по своей природе неизменяемы, поэтому структуры данных обычно представляют собой персистентные структуры данных. Их производительность зависит от механизма совместного использования и сборки мусора, предоставляемого системой Prolog. Расширения для неинстанцированных термов Prolog не всегда возможны из-за экспоненциального роста пространства поиска. Отложенные цели могут смягчить эту проблему. Однако некоторые системы Prolog всё же предоставляют деструктивные операции, такие как setarg/3, которые могут иметь различные реализации: с копированием или без, с отслеживанием изменения состояния или без. В некоторых случаях setarg/3 используется для создания нового декларативного уровня, например, решателя ограничений.

Скала

Язык программирования Scala поощряет использование неизменяемых структур данных для реализации программ в "объектно-функциональном стиле". Scala содержит реализации множества неизменяемых структур данных, включая связные списки, красно-чёрные деревья, а также персистентные хеш-массивы, реализованные в виде tries, как это было представлено в Clojure.

Сбор мусора

Поскольку постоянные структуры данных часто реализуются таким образом, что последовательные версии структуры данных используют общую базовую память, эффективное использование таких структур данных обычно требует какой-либо формы автоматической системы сборки мусора, например, подсчета ссылок или алгоритма «пометить и подметить». На некоторых платформах, где применяются постоянные структуры данных, существует возможность отказаться от сборки мусора, что, хотя и может привести к утечкам памяти, в определенных случаях способно положительно повлиять на общую производительность приложения.