Постоянная структура данных

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

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

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

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

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

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

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

Тип структуры данных, в которой пользователь может запросить любую версию структуры, но может обновить только последнюю версию.

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

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

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

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

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

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

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

Жировый узел

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

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

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

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

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

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

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

Комбинация

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

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

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

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

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

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

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

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

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

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

Копирование пути — один из простых методов достижения персистентности в определенной структуре данных, такой как двоичные деревья поиска. Хорошо иметь общую стратегию для реализации персистентности, которая работает с любой заданной структурой данных. Чтобы добиться этого, рассмотрим ориентированный граф G. Мы предполагаем, что каждая вершина v в G имеет постоянное число c исходящих ребер, представленных указателями. Каждая вершина имеет метку, представляющую данные. Мы считаем, что вершина имеет ограниченное число d ребер , ведущих в нее, которые мы определяем как inedges( v ). Мы допускаем следующие различные операции над G.

• CREATE-NODE(): создает новую вершину без входящих и исходящих ребер.
• CHANGE-EDGE( v , i , u ): изменяет i ^-е ребро v так, чтобы оно указывало на u
• CHANGE-LABEL( v , x ): изменяет значение данных, хранящихся в v, на x

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

СОЗДАТЬ-УЗЕЛ

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

ИЗМЕНЕНИЕ-КРАЯ

Если предположить, что вызывается CHANGE-EDGE( v , i , u ), то следует рассмотреть два случая.

• В таблице вершины v есть пустая строка : в этом случае мы копируем последнюю строку в таблице и меняем i -е ребро вершины v так, чтобы оно указывало на новую вершину u.
• Таблица вершины v заполнена: В этом случае нам нужно создать новую таблицу. Мы копируем последнюю строку старой таблицы в новую таблицу. Нам нужно выполнить цикл в массиве inedges( v ), чтобы каждая вершина в массиве указывала на новую созданную таблицу. В дополнение к этому нам нужно изменить запись v в inedges(w) для каждой вершины w таким образом, чтобы ребро v,w существовало в графе G .

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

Работает точно так же, как CHANGE-EDGE, за исключением того, что вместо изменения i ^-го ребра вершины мы меняем i ^-ю метку.

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

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

• Создание одной таблицы требует один кредит.
• Каждый вызов CREATE-NODE сопровождается двумя кредитами
• Каждый звонок в CHANGE-EDGE сопровождается одним кредитом

Кредитная схема всегда должна удовлетворять следующему инварианту: Каждая строка каждой активной таблицы хранит один кредит, и таблица имеет то же количество кредитов, что и количество строк. Давайте подтвердим, что инвариант применяется ко всем трем операциям CREATE-NODE, CHANGE-EDGE и CHANGE-LABEL.

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

Подводя итог, мы приходим к выводу, что вызовы CREATE_NODE и вызовы CHANGE_EDGE приведут к созданию таблиц. Поскольку каждая таблица имеет размер без учета рекурсивных вызовов, то заполнение таблицы требует , где дополнительный d-фактор возникает из-за обновления inedges в других узлах. Следовательно, объем работы, требуемый для завершения последовательности операций, ограничен количеством созданных таблиц, умноженным на . Каждая операция доступа может быть выполнена за , и существуют операции с ребрами и метками, поэтому она требует . Мы приходим к выводу, что существует структура данных, которая может завершить любую последовательность CREATE-NODE, CHANGE-EDGE и CHANGE-LABEL за . ${\displaystyle n_{1}}$ ${\displaystyle n_{2}}$ ${\displaystyle 2\cdot n_{1}+n_{2}}$ ${\displaystyle O(d)}$ ${\displaystyle O(d^{2})}$ ${\displaystyle O(d^{2})}$ ${\displaystyle O(Log(d))}$ ${\displaystyle m}$ ${\displaystyle m\cdot O(Log(d))}$ ${\displaystyle n}$ ${\displaystyle O(n\cdot d^{2})+m\cdot O(Log(d))}$

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

Поиск следующего элемента или местоположение точки

Одно из полезных приложений, которое можно эффективно решить с помощью сохранения, — это поиск следующего элемента. Предположим, что есть непересекающиеся отрезки прямых, которые не пересекают друг друга и параллельны оси x. Мы хотим построить структуру данных, которая может запросить точку и вернуть сегмент выше (если таковой имеется). Мы начнем с решения поиска следующего элемента с помощью наивного метода, а затем покажем, как решить его с помощью метода сохранения структуры данных. ${\displaystyle n}$ ${\displaystyle p}$ ${\displaystyle p}$

Наивный метод

Мы начинаем с вертикального отрезка, который начинается в бесконечности, и мы сметаем отрезки слева направо. Мы делаем паузу каждый раз, когда сталкиваемся с конечной точкой этих отрезков. Вертикальные линии разбивают плоскость на вертикальные полосы. Если есть отрезки, то мы можем получить вертикальные полосы, поскольку у каждого отрезка есть конечные точки. Ни один отрезок не начинается и не заканчивается на полосе. Каждый отрезок либо не касается полосы, либо полностью пересекает ее. Мы можем думать о отрезках как о некоторых объектах, которые находятся в некотором отсортированном порядке сверху вниз. Нас волнует, где точка, на которую мы смотрим, вписывается в этот порядок. Мы сортируем конечные точки отрезков по их координатам. Для каждой полосы мы сохраняем подмножество сегментов, которые пересекаются, в словаре. Когда вертикальная линия сметает отрезки, всякий раз, когда она проходит над левой конечной точкой отрезка, мы добавляем ее в словарь. Когда она проходит через правую конечную точку отрезка, мы удаляем ее из словаря. В каждой конечной точке мы сохраняем копию словаря и сохраняем все копии, отсортированные по координатам. Таким образом, у нас есть структура данных, которая может ответить на любой запрос. Чтобы найти сегмент над точкой , мы можем посмотреть на координату , чтобы узнать, к какой копии или полосе он принадлежит. Затем мы можем посмотреть на координату , чтобы найти сегмент над ней. Таким образом, нам нужно два бинарных поиска, один для координаты , чтобы найти полосу или копию, и другой для координаты , чтобы найти сегмент над ней. Таким образом, время запроса занимает . В этой структуре данных пространство является проблемой, поскольку если мы предположим, что у нас есть сегменты, структурированные таким образом, что каждый сегмент начинается до конца любого другого сегмента, то пространство, необходимое для построения структуры с использованием наивного метода, будет . Давайте посмотрим, как мы можем построить другую постоянную структуру данных с тем же временем запроса, но с лучшим пространством. ${\displaystyle n}$ ${\displaystyle 2\cdot n+1}$ ${\displaystyle 2}$ ${\displaystyle x}$ ${\displaystyle s_{i}}$ ${\displaystyle s_{i}}$ ${\displaystyle x}$ ${\displaystyle p}$ ${\displaystyle x}$ ${\displaystyle p}$ ${\displaystyle y}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle O(Log(n))}$ ${\displaystyle O(n^{2})}$

Метод постоянной структуры данных

Мы можем заметить, что на самом деле время в структуре данных, используемой в наивном методе, занимает то, что всякий раз, когда мы переходим от полосы к следующей, нам нужно сделать снимок любой структуры данных, которую мы используем, чтобы поддерживать порядок сортировки. Мы можем заметить, что как только мы получаем сегменты, которые пересекаются , при переходе к либо одна вещь выходит, либо одна вещь входит. Если разница между тем, что находится в , и тем, что находится в , составляет всего одну вставку или удаление, то не стоит копировать все из в . Хитрость в том, что поскольку каждая копия отличается от предыдущей только одной вставкой или удалением, то нам нужно копировать только те части, которые изменяются. Предположим, что у нас есть дерево с корнем в . Когда мы вставляем ключ в дерево, мы создаем новый лист, содержащий . Выполнение поворотов для повторной балансировки дерева изменит только узлы пути от до . Перед вставкой ключа в дерево мы копируем все узлы на пути от до . Теперь у нас есть 2 версии дерева: исходная, которая не содержит , и новая, которая содержит и чей корень является копией корня . Поскольку копирование пути из в не увеличивает время вставки более чем на постоянный множитель, то вставка в постоянную структуру данных занимает время. Для удаления нам нужно найти, какие узлы будут затронуты удалением. Для каждого узла, затронутого удалением, мы копируем путь из корня в . Это предоставит новое дерево, корень которого является копией корня исходного дерева. Затем мы выполняем удаление в новом дереве. В итоге у нас будет 2 версии дерева. Исходная, которая содержит , и новая, которая не содержит . Поскольку любое удаление изменяет только путь из корня в , и любой подходящий алгоритм удаления выполняется за , таким образом, удаление в постоянной структуре данных занимает . Каждая последовательность вставки и удаления приведет к созданию последовательности словарей или версий или деревьев , каждое из которых является результатом операций . Если каждый содержит элементы, то поиск в каждом занимает . Используя эту постоянную структуру данных, мы можем решить следующую задачу поиска элемента за время и пространство запроса вместо . Ниже вы найдете исходный код примера, относящегося к следующей задаче поиска. ${\displaystyle s_{i}}$ ${\displaystyle s_{i+1}}$ ${\displaystyle s_{i}}$ ${\displaystyle s_{i+1}}$ ${\displaystyle s_{i}}$ ${\displaystyle s_{i+1}}$ ${\displaystyle T}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle T}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle T}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle T}$ ${\displaystyle k}$ ${\displaystyle T}$ ${\displaystyle O(Log(n))}$ ${\displaystyle v}$ ${\displaystyle v}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle v}$ ${\displaystyle O(Log(n))}$ ${\displaystyle O(Log(n))}$ ${\displaystyle S_{1},S_{2},\dots S_{i}}$ ${\displaystyle S_{i}}$ ${\displaystyle S_{1},S_{2},\dots S_{i}}$ ${\displaystyle S_{i}}$ ${\displaystyle m}$ ${\displaystyle S_{i}}$ ${\displaystyle O(Log(m))}$ ${\displaystyle O(Log(n))}$ ${\displaystyle O(n\cdot Log(n))}$ ${\displaystyle O(n^{2})}$

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

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

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

Существуют также постоянные структуры данных, которые используют деструктивные ^{[ требуется разъяснение ]} операции, что делает их невозможными для эффективной реализации в чисто функциональных языках (например, Haskell вне специализированных монад, таких как state или IO), но возможными в таких языках, как C или Java. Этих типов структур данных часто можно избежать с помощью другого дизайна. Одним из основных преимуществ использования чисто постоянных структур данных является то, что они часто ведут себя лучше в многопоточных средах.

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

Односвязные списки являются основной структурой данных в функциональных языках. ^[10] Некоторые языки, производные от ML , такие как Haskell , являются чисто функциональными, поскольку после выделения узла в списке его нельзя изменить, а только скопировать, сделать ссылкой или уничтожить сборщиком мусора , когда на него ничего не ссылается. (Обратите внимание, что сам ML не является чисто функциональным, но поддерживает подмножество неразрушающих операций со списками, что также верно в диалектах функционального языка Lisp (обработка LISt), таких как Scheme и Racket .)

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

хс = [0, 1, 2]ys = [3, 4, 5]

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

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

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

zs = xs ++ ys

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

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

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

Деревья

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

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

хс = [а, б, в, г, е, ж, з]

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

Функция, которая вставляет данные в двоичное дерево и сохраняет инвариант, выглядит следующим образом:

 забавная  вставка  ( x ,  E )  =  T  ( E ,  x ,  E )  |  вставка  ( x ,  s  как  T  ( a ,  y ,  b ))  =  если  x  <  y  тогда  T  ( вставка  ( x ,  a ),  y ,  b )  иначе  если  x  >  y  тогда  T  ( a ,  y ,  вставка  ( x ,  b ))  иначе  s

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

ys = вставить ("e", xs)

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

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

Код

Репозиторий GitHub, содержащий реализации постоянных BST с использованием толстых узлов, копирования при записи и методов копирования путей.

Чтобы использовать постоянные реализации BST, просто клонируйте репозиторий и следуйте инструкциям, приведенным в файле README.

Ссылка: https://github.com/DesaultierMAKK/PersistentBST

Постоянный хэш-массив, отображающий trie

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

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

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

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

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

Хаскелл

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

В своей стандартной библиотеке Haskell имеет эффективные постоянные реализации для связанных списков, ^[16] карт (реализованных как деревья сбалансированного размера) ^[17] и множеств ^[18] среди других. ^[19]

Кложур

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

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

Эти структуры данных формируют основу поддержки параллельных вычислений в Clojure, поскольку они позволяют легко повторять операции, чтобы обойти гонки данных и атомарную семантику сравнения и обмена . ^[23]

Вяз

Язык программирования Elm является чисто функциональным, как и Haskell, который делает все его структуры данных постоянными по необходимости. Он содержит постоянные реализации связанных списков, а также постоянные массивы, словари и множества. ^[24]

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

Ява

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

JavaScript

Популярный JavaScript frontend framework React часто используется вместе с системой управления состоянием, которая реализует архитектуру Flux, ^{[27] [28]} популярной реализацией которой является библиотека JavaScript Redux . Библиотека Redux вдохновлена ​​шаблоном управления состоянием, используемым в языке программирования Elm, что означает, что она требует, чтобы пользователи рассматривали все данные как постоянные. ^[29] В результате проект Redux рекомендует пользователям в определенных случаях использовать библиотеки для принудительных и эффективных постоянных структур данных. Сообщается, что это обеспечивает большую производительность, чем при сравнении или создании копий обычных объектов JavaScript. ^[30]

Одна из таких библиотек постоянных структур данных Immutable.js основана на структурах данных, предоставленных и популяризированных Clojure и Scala. ^[31] Она упоминается в документации Redux как одна из возможных библиотек, которые могут обеспечить принудительную неизменяемость. ^[30] Mori.js привносит в JavaScript структуры данных, похожие на те, что есть в Clojure. ^[32] Immer.js привносит интересный подход, при котором «создается следующее неизменяемое состояние путем мутации текущего». ^[33] Immer.js использует собственные объекты JavaScript, а не эффективные постоянные структуры данных, и это может вызвать проблемы с производительностью, если размер данных большой.

Пролог

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

Некоторые системы Prolog, тем не менее, предоставляют деструктивные операции, такие как setarg/3, которые могут быть разных видов, с копированием/без копирования и с/без обратного отслеживания изменения состояния. Есть случаи, когда setarg/3 используется для предоставления нового декларативного слоя, например, решателя ограничений. ^[35]

Скала

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

Сбор мусора

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

Смотрите также

• Копирование при записи
• Навигационная база данных
• Постоянные данные
• Структуры ретроактивных данных
• Чисто функциональная структура данных

Ссылки

1. Driscoll JR, Sarnak N, Sleator DD, Tarjan RE (1986). "Создание постоянных структур данных". Труды восемнадцатого ежегодного симпозиума ACM по теории вычислений - STOC '86 . стр. 109–121. CiteSeerX  10.1.1.133.4630 . doi :10.1145/12130.12142. ISBN 978-0-89791-193-1. S2CID  364871.
2. Каплан, Хаим (2001). «Постоянные структуры данных». Справочник по структурам данных и приложениям .
3. Коншон, Сильвен; Филлиатр, Жан-Кристоф (2008), «Полуперсистентные структуры данных», Языки и системы программирования , Конспект лекций по информатике, т. 4960, Springer Berlin Heidelberg, стр. 322–336, doi : 10.1007/978-3-540-78739-6_25 , ISBN 9783540787389
4. Тиарк, Багвелл, Филип Ромпф (2011). RRB-деревья: эффективные неизменяемые векторы . OCLC  820379112.{{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка )
5. Бродал, Герт Столтинг; Макрис, Христос; Цихлас, Костас (2006), "Чисто функциональные худшие постоянные времени категорируемые отсортированные списки", Алгоритмы – ESA 2006 , Lecture Notes in Computer Science, т. 4168, Springer Berlin Heidelberg, стр. 172–183, CiteSeerX 10.1.1.70.1493 , doi :10.1007/11841036_18, ISBN  9783540388753
6. Ленхоф, Ханс-Петер; Смид, Михиль (1994). «Использование постоянных структур данных для добавления ограничений диапазона к задачам поиска». RAIRO - Теоретическая информатика и приложения . 28 (1): 25–49. doi :10.1051/ita/1994280100251. hdl : 11858/00-001M-0000-0014-AD4F-B . ISSN  0988-3754.
7. Нил Сарнак; Роберт Э. Тарьян (1986). «Определение местоположения точки на плоскости с использованием деревьев постоянного поиска» (PDF) . Сообщения ACM . 29 (7): 669–679. doi :10.1145/6138.6151. S2CID  8745316. Архивировано из оригинала (PDF) 2015-10-10 . Получено 2011-04-06 .
8. Крис Окасаки. «Чисто функциональные структуры данных (диссертация)» (PDF) . {{cite journal}}: Цитировать журнал требует |journal=( помощь )
9. Лильензин, Олле (2013). «Конфлюэнтно персистентные множества и отображения». arXiv : 1301.3388 . Bibcode :2013arXiv1301.3388L. {{cite journal}}: Цитировать журнал требует |journal=( помощь )
10. Этот пример взят из Okasaki. См. библиографию.
11. BoostCon (2017-06-13), C++Now 2017: Фил Нэш «Священный Грааль!? Постоянный хэш-массив-отображенный Trie для C++», архивировано из оригинала 2021-12-21 , извлечено 2018-10-22
12. Фил, Багвелл (2001). «Идеальные хэш-деревья». {{cite journal}}: Цитировать журнал требует |journal=( помощь )
13. "Мы уже там?". InfoQ . Получено 22.10.2018 .
14. Steindorfer, Michael J.; Vinju, Jurgen J. (2015-10-23). ​​«Оптимизация попыток отображения хэш-массива для быстрых и экономичных неизменяемых коллекций JVM». ACM SIGPLAN Notices . 50 (10): 783–800. doi :10.1145/2814270.2814312. ISSN  0362-1340. S2CID  10317844.
15. "Язык Haskell". www.haskell.org . Получено 2018-10-22 .
16. "Data.List". hackage.haskell.org . Получено 2018-10-23 .
17. "Data.Map.Strict". hackage.haskell.org . Получено 2018-10-23 .
18. "Data.Set". hackage.haskell.org . Получено 2018-10-23 .
19. "Производительность/Массивы - HaskellWiki". wiki.haskell.org . Получено 2018-10-23 .
20. "Clojure - Различия с другими языками Lisp". clojure.org . Получено 23.10.2018 .
21. "Clojure - Структуры данных". clojure.org . Получено 2018-10-23 .
22. "Ключевой доклад: Ценность ценностей". InfoQ . Получено 2018-10-23 .
23. "Clojure - Атомы". clojure.org . Получено 2018-11-30 .
24. "core 1.0.0". package.elm-lang.org . Получено 2018-10-23 .
25. "blog/blazing-fast-html-round-two". elm-lang.org . Получено 2018-10-23 .
26. "Постоянные (неизменяемые) коллекции для Java и Kotlin". github.com . Получено 2023-12-13 .
27. "Flux | Архитектура приложений для создания пользовательских интерфейсов". facebook.github.io . Получено 2018-10-23 .
28. Мора, Осмел (2016-07-18). "Как обрабатывать состояние в React". Экосистема React . Получено 2018-10-23 .
29. "Прочтите меня - Redux". redux.js.org . Получено 2018-10-23 .
30. "Неизменяемые данные - Redux". redux.js.org . Получено 2018-10-23 .
31. "Immutable.js". facebook.github.io . Архивировано из оригинала 2015-08-09 . Получено 2018-10-23 .
32. "Мори".
33. "Погружение". Гитхаб . 26 октября 2021 г.
34. Джамбулян, Ара М.; Буазумо, Патрис (1993), Реализация Пролога - Патрис Буазумо, Princeton University Press, ISBN 9780691637709
35. Использование Меркурия для реализации решателя конечных областей - Хенк Вандекастил, Барт Демоен, Иоахим Ван дер Аувера, 1999
36. "Суть объектно-функционального программирования и практический потенциал Scala - блог codecentric AG". Блог codecentric AG . 2015-08-31 . Получено 2018-10-23 .
37. ClojureTV (2013-01-07), Экстремальная сообразительность: функциональные структуры данных в Scala - Дэниел Спивак , получено 2018-10-23^{[ мертвая ссылка на YouTube ]}
38. "Владимир Костюков - Записи/Слайды". костюков.нет . Проверено 30 ноября 2018 г.
39. "Неизменяемые объекты и сборка мусора". wiki.c2.com . Получено 2018-11-30 .
40. "Последний рубеж производительности Java: удаление сборщика мусора". InfoQ . Получено 2018-11-30 .

Внешние ссылки

• Облегченная реализация постоянных красно-черных деревьев на Java
• Эффективные постоянные структуры в C#