Постоянная структура данных - Persistent data structure

В вычислении , А Стойкая структура данных или не эфемерная структура данных является структурой данных , которая всегда сохраняет предыдущую версию себя , когда он изменяется. Такие структуры данных фактически неизменяемы , поскольку их операции (явно) не обновляют структуру на месте, а вместо этого всегда создают новую обновленную структуру. Этот термин был введен в статье Дрисколла, Сарнака, Слеатора и Тарьянса 1986 года.

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

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

Частичное или полное постоянство

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

Способы сохранения предыдущих версий

Копирование при записи

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

Жирный узел

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

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

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

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

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

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

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

Комбинация

Дрисколл, Сарнак, Слеатор , Тарджан придумали способ объединить методы толстых узлов и копирования пути, достигнув O (1) замедления доступа и O (1) пространственной и временной сложности модификации.

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

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

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

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

Сложность комбинации

Время и место для модификаций требуют амортизированного анализа. Модификация занимает O (1) амортизированного пространства и O (1) амортизированного времени. Чтобы понять, почему, используйте потенциальную функцию ϕ, где ϕ (T) - количество полных активных узлов в T. Активные узлы T - это просто узлы, доступные из текущего корня в текущее время (то есть после последней модификации). Полные активные узлы - это активные узлы, чьи поля модификации заполнены.

Каждая модификация включает в себя некоторое количество копий, скажем k, за которым следует одно изменение в поле модификации. Рассмотрим каждую из k копий. Каждый стоит O (1) пространства и времени, но уменьшает потенциальную функцию на единицу. (Во-первых, копируемый узел должен быть полным и активным, чтобы он вносил свой вклад в потенциальную функцию. Однако потенциальная функция будет отключена только в том случае, если старый узел недоступен в новом дереве. Но известно, что он недоступен в новом дереве - следующим шагом в алгоритме будет изменение родительского узла, чтобы он указывал на копию. Наконец, известно, что поле модификации копии пусто. Таким образом, заменен полный рабочий узел заменяется пустым живым узлом, и ϕ уменьшается на единицу.) Последний шаг заполняет поле модификации, которое стоит O (1) времени и увеличивает ϕ на единицу.

Суммируя все вместе, изменение ϕ равно ∆ϕ = 1− k. Таким образом, алгоритм занимает O (k + Δϕ) = O (1) пространства и O (k + Δϕ +1) = O (1) раз

Обобщенная форма настойчивости

Копирование пути - один из простых методов достижения постоянства в определенной структуре данных, такой как двоичные деревья поиска. Приятно иметь общую стратегию реализации персистентности, которая работает с любой заданной структурой данных. Для этого мы рассматриваем ориентированный граф . Мы предполагаем, что каждая вершина в имеет постоянное количество исходящих ребер, которые представлены указателями. Каждая вершина имеет метку, представляющую данные. Мы считаем, что вершина имеет ограниченное число ребер, ведущих в нее, которые мы определяем как выступы ( ). Мы разрешаем следующие различные операции с . ${\ displaystyle G}$ ${\ displaystyle v}$ ${\ displaystyle G}$ ${\ displaystyle c}$ ${\ displaystyle d}$ ${\ displaystyle v}$ ${\ displaystyle G}$

 * CREATE-NODE(): Creates a new vertex with no incoming or outgoing edges.
 * CHANGE-EDGE( $v$ ,  $i$ ,  $u$ ): Changes the  $i^{th}$  edge of  $v$  to point to  $u$ 
 * CHANGE-LABEL( $v$ ,  $x$ ): Changes the value of the data stored at  $v$  to  $x$

Любая из вышеперечисленных операций выполняется в определенное время, и цель представления постоянного графа - иметь доступ к любой версии в любой момент времени. Для этого мы определяем таблицу для каждой вершины в . Таблица содержит столбцы и строки. Каждая строка содержит, помимо указателей для исходящих ребер, метку, которая представляет данные в вершине и время, в которое была выполнена операция. В дополнение к этому есть массив inedges ( ), который отслеживает все входящие ребра в . Когда таблица заполнена, можно создать новую таблицу со строками. Старая таблица становится неактивной, а новая таблица становится активной. ${\ displaystyle G}$ ${\ displaystyle v}$ ${\ displaystyle G}$ ${\ displaystyle c}$ ${\ displaystyle d + 1}$ ${\ displaystyle t}$ ${\ displaystyle v}$ ${\ displaystyle v}$ ${\ displaystyle d + 1}$

СОЗДАТЬ УЗЕЛ

Вызов CREATE-NODE создает новую таблицу и устанавливает для всех ссылок значение null.

ИЗМЕНЕНИЕ

Если мы предположим , что переключающий EDGE ( , , ) называется то есть рассмотреть два случая. ${\ displaystyle v}$ ${\ displaystyle i}$ ${\ displaystyle u}$

 * There is an empty row in the table of the vertex  $v$ : In this case we copy the last row in the table and we change the  $i^{th}$  edge of vertex  $v$  to point to the new vertex  $u$ 
 * Table of the vertex  $v$  is full: In this case we need to create a new table. We copy the last row of the old table into the new table. We need to loop in the array inedges( $v$ ) in order to let each vertex in the array point to the new table created. In addition to that we need to change the entry  $v$  in the inedges(w) for every vertex  $w$  such that edge  $v,w$  exists in the graph  $G$ .

ИЗМЕНИТЬ-ЭТИКЕТКУ

Он работает точно так же, как CHANGE_EDGE, за исключением того, что вместо изменения края вершины мы меняем метку. ${\ displaystyle i ^ {th}}$

Эффективность обобщенной устойчивой структуры данных

Чтобы определить эффективность предложенной выше схемы, мы используем аргумент, определенный как кредитная схема. Кредит представляет собой валюту. Например, кредит можно использовать для оплаты стола. Аргумент гласит следующее:

 *  The creation of one table requires one credit
 *  Each call to CREATE_NODE comes with two credits
 *  Each call to CHANGE_EDGE comes with one credit

Схема кредитования всегда должна удовлетворять следующему инварианту: каждая строка каждой активной таблицы хранит один кредит, а таблица имеет такое же количество кредитов, что и количество строк. Подтвердим, что инвариант применяется ко всем трем операциям CREATE_NODE, CHANGE_EDGE и CHANGE-LABEL.

CREATE-NODE: получает два кредита, один используется для создания таблицы, а другой присваивается одной строке, добавляемой в таблицу. Таким образом, инвариант сохраняется.
CHANGE_EDGE: необходимо рассмотреть два случая. Первый случай возникает, когда в таблице все еще есть хотя бы одна пустая строка. В этом случае для вновь вставленной строки используется один кредит. Второй случай возникает, когда стол заполнен. В этом случае старая таблица становится неактивной, и кредиты преобразуются в новую таблицу в дополнение к одному кредиту, полученному в результате вызова CHANGE-EDGE. Итак, у нас есть кредиты. Один кредит будет использован для создания новой таблицы. Еще один кредит будет использован для новой строки, добавленной в таблицу, а оставшиеся кредиты используются для обновления таблиц других вершин, которые должны указывать на новую таблицу. Делаем вывод, что инвариант сохраняется. ${\ displaystyle d + 1}$ ${\ displaystyle d + 2}$ ${\ displaystyle d}$
CHANGE-LABEL: работает точно так же, как CHANGE_EDGE.

Подводя итог, мы заключаем, что вызовы CREATE_NODE и CHANGE_EDGE приведут к созданию таблиц. ${\ displaystyle n_ {1}}$ ${\ displaystyle n_ {2}}$ ${\ displaystyle 2 \ cdot n_ {1} + n_ {2}}$

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

Возможно, самая простая постоянная структура данных - это односвязный список или список на основе cons , простой список объектов, каждый из которых содержит ссылку на следующий в списке. Это повторяется , потому что хвост списка может быть принято, то есть последние K элементов для некоторых к , и новых узлы могут быть добавлены перед ним. Хвост не будет дублироваться, вместо этого он станет общим для старого и нового списков. Пока содержимое хвоста неизменяемо, это совместное использование будет невидимым для программы.

Многие распространенные структуры данных на основе ссылок, такие как красно-черные деревья , стеки и трепы , можно легко адаптировать для создания постоянной версии. Некоторым другим требуется немного больше усилий, например: очереди , очереди и расширения, включая min-deques (которые имеют дополнительную операцию O (1) min, возвращающую минимальный элемент) и deques с произвольным доступом (которые имеют дополнительную операцию произвольного доступа с сублинейная, чаще всего логарифмическая, сложность).

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

Связанные списки

Односвязные списки - это простая структура данных в функциональных языках. Некоторые языки, производные от ML , такие как Haskell , являются чисто функциональными, потому что после того, как узел в списке был выделен, его нельзя изменить, а только скопировать, указать или уничтожить сборщиком мусора, когда на него ничего не ссылается. (Обратите внимание , что сам по себе ML является не чисто функциональным, но поддерживает неразрушающий список операции подмножества, которое также верно в Лиспе (Лисп) функциональных диалекты языка как Scheme и рэкет .)

Рассмотрим два списка:

xs = [0, 1, 2]
ys = [3, 4, 5]

Они будут представлены в памяти следующим образом:

где кружок указывает узел в списке (стрелка вниз представляет второй элемент узла, который является указателем на другой узел).

Теперь объединим два списка:

zs = xs ++ ys

приводит к следующей структуре памяти:

Обратите внимание, что узлы в списке xsбыли скопированы, но узлы ysявляются общими. В результате исходные списки ( xsи ys) сохраняются и не изменяются.

Причина копирования заключается в том, что последний узел в xs(узел, содержащий исходное значение 2) нельзя изменить так, чтобы он указывал на начало ys, потому что это изменило бы значение xs.

Деревья

Рассмотрим двоичное дерево поиска , где каждый узел в дереве имеет рекурсивный инвариант, согласно которому все подузлы, содержащиеся в левом поддереве, имеют значение, меньшее или равное значению, хранящемуся в узле, а подузлы, содержащиеся в правом поддереве, имеют значение значение, превышающее значение, хранящееся в узле.

Например, набор данных

xs = [a, b, c, d, f, g, h]

может быть представлено следующим двоичным деревом поиска:

Функция, которая вставляет данные в двоичное дерево и поддерживает инвариант:

 fun insert (x, E) = T (E, x, E)
   | insert (x, s as T (a, y, b)) =
        if x < y then T (insert (x, a), y, b)
        else if x > y then T (a, y, insert (x, b))
        else s

После выполнения

ys = insert ("e", xs)

Производится следующая конфигурация:

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

Постоянный хэш-массив сопоставленного дерева

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

Попытки сопоставления хэш-массива были первоначально описаны в статье Фила Багвелла 2001 года, озаглавленной «Идеальные хеш-деревья». В этом документе представлена изменяемая хеш-таблица, в которой «время вставки, поиска и удаления является небольшим и постоянным, независимо от размера набора ключей, операции - O (1). Небольшое время наихудшего случая для операций вставки, поиска и удаления может быть гарантировано и пропущено. обходятся дешевле, чем успешные поиски ». Затем эта структура данных была изменена Ричем Хики, чтобы она стала полностью устойчивой для использования в языке программирования Clojure .

Концептуально попытки сопоставления хэш-массива работают аналогично любому общему дереву в том смысле, что они хранят узлы иерархически и извлекают их, следуя пути вниз к определенному элементу. Ключевое отличие состоит в том, что попытки сопоставления хэш-массива сначала используют хеш-функцию для преобразования своего ключа поиска в целое число (обычно 32- или 64-разрядное). Затем определяется путь вниз по дереву с использованием срезов двоичного представления этого целого числа для индексации в разреженный массив на каждом уровне дерева. Листовые узлы дерева ведут себя аналогично сегментам, используемым для построения хеш-таблиц, и могут содержать или не содержать несколько кандидатов в зависимости от хеш-коллизий .

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

Использование в языках программирования

Haskell

Haskell - это чисто функциональный язык, поэтому он не допускает изменений. Следовательно, все структуры данных в языке являются постоянными, поскольку невозможно не сохранить предыдущее состояние структуры данных с функциональной семантикой. Это связано с тем, что любое изменение структуры данных, которое сделало бы предыдущие версии структуры данных недействительными, нарушило бы ссылочную прозрачность .

В своей стандартной библиотеке Haskell имеет эффективные постоянные реализации для связанных списков, карт (реализованных в виде деревьев со сбалансированным размером) и наборов среди прочего.

Clojure

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

Разработчики языка 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 он упоминается как одна из возможных библиотек, которые могут обеспечить принудительную неизменяемость. Mori.js переносит в JavaScript структуры данных, аналогичные тем, что есть в Clojure. Immer.js предлагает интересный подход, при котором «создается следующее неизменяемое состояние, изменяя текущее». Immer.js использует собственные объекты JavaScript, а не эффективные постоянные структуры данных, и это может вызвать проблемы с производительностью при большом размере данных.

Пролог

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

Тем не менее, некоторые системы Prolog предоставляют деструктивные операции, такие как setarg / 3, которые могут иметь разные разновидности, с / без копирования и с / без обратного отслеживания изменения состояния. Бывают случаи, когда setarg / 3 используется для предоставления нового декларативного уровня, например, решателя ограничений.

Scala

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

Вывоз мусора

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

Languages

In other projects