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

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

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

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

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

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

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

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

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

Одним из методов создания постоянной структуры данных является использование предоставляемой платформой эфемерной структуры данных, такой как массив , для хранения данных в структуре данных и полное копирование этой структуры данных с использованием семантики копирования при записи для любых обновлений данных. состав. Это неэффективный метод, поскольку для каждой записи необходимо копировать всю структуру резервных данных, что приводит к худшему варианту производительности 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. Итак, в общей сложности у нас есть кредиты. Один кредит будет использован для создания новой таблицы. Еще один кредит будет использован для новой строки, добавленной в таблицу, а оставшиеся d кредитов будут использованы для обновления таблиц других вершин, которые должны указывать на новую таблицу. Делаем вывод, что инвариант сохраняется. ${\displaystyle d+1}$ ${\displaystyle d+2}$
• CHANGE-LABEL: Работает точно так же, как CHANGE-EDGE.

Подводя итог, мы приходим к выводу, что вызовы CREATE_NODE и вызовы CHANGE_EDGE приведут к созданию таблиц. Поскольку каждая таблица имеет размер без учета рекурсивных вызовов, то для заполнения таблицы требуется, чтобы дополнительный d-фактор возникал из-за обновления внутренних ребер в других узлах. Таким образом, объем работы, необходимой для выполнения последовательности операций, ограничен количеством созданных таблиц, умноженным на . Каждая операция доступа может быть выполнена, и существуют операции по краям и меткам, поэтому для этого требуется . Мы пришли к выводу, что существует структура данных, которая может завершить любую последовательность 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 версии дерева. Исходный, который содержит, и новый, который не содержит . Поскольку любое удаление изменяет только путь от корня до и запускается любой соответствующий алгоритм удаления , удаление в постоянной структуре данных занимает . Каждая последовательность вставки и удаления приведет к созданию последовательности словарей, версий или деревьев, каждое из которых является результатом операций . Если каждый содержит элементы, то поиск в каждом занимает . Используя эту постоянную структуру данных, мы можем решить следующую проблему поиска элемента во времени и пространстве запроса вместо . Ниже вы найдете исходный код примера, связанного со следующей задачей поиска. ${\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 , простой список объектов, каждый из которых содержит ссылку на следующий в списке. Это постоянно, поскольку можно взять хвост списка, то есть последние k элементов для некоторого k , и перед ним можно добавить новые узлы. Хвост не будет дублироваться, а будет использоваться как старым, так и новым списком. Пока содержимое хвоста неизменно, это совместное использование будет невидимо для программы.

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

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

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

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

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

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

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

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

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

зз = хз ++ ус

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

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

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

Деревья

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

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

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

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

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

 забавная  вставка  ( Икс ,  E )  знак равно  Т  ( E ,  Икс ,  E )  |  вставить  ( x ,  s  as  T  ( a ,  y ,  b ))  =  если  x  <  y  то  T  ( вставить  ( x ,  a ),  y ,  b )  иначе  если  x  >  y  то  T  ( a ,  y ,  вставить  ( x ,  б ))  еще  с

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

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

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

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

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

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

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

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

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

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

Хаскелл

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

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

Кложур

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

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

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

Вяз

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

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

Джава

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

JavaScript

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

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

Пролог

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

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

Скала

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

Вывоз мусора

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

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

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

Рекомендации

1. Дрисколл-младший, Сарнак Н., Слиатор Д.Д., Тарьян Р.Э. (1986). «Сохранение структур данных». Материалы восемнадцатого ежегодного симпозиума ACM по теории вычислений - STOC '86 . стр. 109–121. CiteSeerX  10.1.1.133.4630 . дои : 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-деревья: эффективные неизменяемые векторы . ОСЛК  820379112.{{cite book}}: CS1 maint: multiple names: authors list (link)
5. Бродал, Герт Столтинг; Макрис, Христос; Цихлас, Костас (2006), «Чисто функциональные сортированные списки для наихудшего случая с постоянным временем, которые можно объединить», Алгоритмы - ESA 2006 , Конспекты лекций по информатике, том. 4168, Springer Berlin Heidelberg, стр. 172–183, CiteSeerX 10.1.1.70.1493 , doi : 10.1007/11841036_18, ISBN  9783540388753
6. Нил Сарнак; Роберт Э. Тарьян (1986). «Расположение плоской точки с использованием постоянных деревьев поиска» (PDF) . Коммуникации АКМ . 29 (7): 669–679. дои : 10.1145/6138.6151. S2CID  8745316. Архивировано из оригинала (PDF) 10 октября 2015 г. Проверено 6 апреля 2011 г.
7. Крис Окасаки. «Чисто функциональные структуры данных (диссертация)» (PDF) . {{cite journal}}: Требуется цитировать журнал |journal=( помощь )
8. Лильензин, Олле (2013). «Слитно устойчивые множества и карты». arXiv : 1301.3388 . Бибкод : 2013arXiv1301.3388L. {{cite journal}}: Требуется цитировать журнал |journal=( помощь )
9. Этот пример взят из Окасаки. См. библиографию.
10. BoostCon (13 июня 2017 г.), C++Now 2017: Фил Нэш «Святой Грааль !? Постоянная таблица с отображением хэш-массива для C++», заархивировано из оригинала 21 декабря 2021 г. , получено в 2018 г. -10-22
11. Фил, Бэгвелл (2001). «Идеальные хэш-деревья». {{cite journal}}: Требуется цитировать журнал |journal=( помощь )
12. «Мы уже там?». ИнфоQ . Проверено 22 октября 2018 г.
13. Стейндорфер, Майкл Дж.; Винью, Юрген Дж. (23 октября 2015 г.). «Оптимизация попыток отображения хэш-массива для быстрых и экономичных неизменяемых коллекций JVM». Уведомления ACM SIGPLAN . 50 (10): 783–800. дои : 10.1145/2814270.2814312. ISSN  0362-1340. S2CID  10317844.
14. «Язык Хаскель» . www.haskell.org . Проверено 22 октября 2018 г.
15. "Данные.Список". hackage.haskell.org . Проверено 23 октября 2018 г.
16. "Data.Map.Strict". hackage.haskell.org . Проверено 23 октября 2018 г.
17. "Данные.Набор". hackage.haskell.org . Проверено 23 октября 2018 г.
18. "Производительность/Массивы - HaskellWiki" . wiki.haskell.org . Проверено 23 октября 2018 г.
19. «Clojure — различия с другими Lisp». Clojure.org . Проверено 23 октября 2018 г.
20. «Clojure — Структуры данных» . Clojure.org . Проверено 23 октября 2018 г.
21. «Основной доклад: ценность ценностей». ИнфоQ . Проверено 23 октября 2018 г.
22. "Clojure - Атомы" . Clojure.org . Проверено 30 ноября 2018 г.
23. «ядро 1.0.0». package.elm-lang.org . Проверено 23 октября 2018 г.
24. "блог/blazing-fast-html-round-two" . elm-lang.org . Проверено 23 октября 2018 г.
25. «Постоянные (неизменяемые) коллекции для Java и Kotlin». github.com . Проверено 13 декабря 2023 г.
26. «Flux | Архитектура приложений для создания пользовательских интерфейсов» . facebook.github.io . Проверено 23 октября 2018 г.
27. Мора, Осмель (18 июля 2016 г.). «Как обрабатывать состояние в React». Реагировать на экосистему . Проверено 23 октября 2018 г.
28. "Прочти меня - Redux" . redux.js.org . Проверено 23 октября 2018 г.
29. «Неизменяемые данные — Redux». redux.js.org . Проверено 23 октября 2018 г.
30. "Неизменяемый.js". facebook.github.io . Архивировано из оригинала 9 августа 2015 г. Проверено 23 октября 2018 г.
31. "Мори".
32. "Погружение". Гитхаб . 26 октября 2021 г.
33. Джамбулян, Ара М.; Буазюмо, Патрис (1993), Реализация Пролога - Патрис Буазюмо, Princeton University Press, ISBN 9780691637709
34. Использование Меркурия для реализации решателя конечных областей - Хенк Вандекастил, Барт Демоен, Иоахим Ван дер Аувера, 1999
35. «Сущность объектно-функционального программирования и практический потенциал Scala - кодоцентричный блог AG» . Блог codecentric AG . 31 августа 2015 г. Проверено 23 октября 2018 г.
36. ClojureTV (07.01.2013), Чрезвычайная умность: функциональные структуры данных в Scala - Дэниел Спивак , получено 23 октября 2018 г.^{[ мертвая ссылка на YouTube ]}
37. "Владимир Костюков - Записи/Слайды". костюков.нет . Проверено 30 ноября 2018 г.
38. «Неизменяемые объекты и сбор мусора» . wiki.c2.com . Проверено 30 ноября 2018 г.
39. «Последний рубеж производительности Java: удалите сборщик мусора» . ИнфоQ . Проверено 30 ноября 2018 г.

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

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