Постоянный массив - Persistent array

В Информатика, а точнее в структура данных, апостоянный массив это постоянная структура данных со свойствами, похожими на (непостоянный) множество. Таким образом, после обновления значения в постоянном массиве существует два постоянных массива. Один постоянный массив, в котором учитывается обновление, и тот, который равен массиву до обновления.

Разница между постоянными массивами и массивами

Массив${\displaystyle \mathrm {ar} =[e_{0},\dots ,e_{n-1}]}$ это структура данных с фиксированным номером п элементов ${\displaystyle e_{0},\dots ,e_{n-1}}$. Ожидается, что с учетом массива ар и индекс ${\displaystyle 0\leq i<n}$, Значение ${\displaystyle e_{i}}$ можно быстро получить. Эта операция называетсяискать. Кроме того, учитывая массив ар, индекс${\displaystyle 0\leq i<n}$ и новое значение v, новый массив ar2 с удовлетворением ${\displaystyle [e_{0},\dots ,e_{i-1},v,e_{i+1},\dots ,e_{n-1}]}$ можно создать быстро. Эта операция называется Обновить. Основное различие между постоянными и непостоянными массивами состоит в том, что в непостоянных массивах массив ар разрушается при создании ar2.

Например, рассмотрим следующий псевдокод.

множество = [0, 0, 0]updated_array = множество.update (0, 8)other_array = множество.update (1, 3)last_array = updated_array.update (2, 5)

В конце выполнения значение множество по-прежнему [0, 0, 0], значение update_array равно [8, 0, 0], значение other_arrayравно [0, 3, 0], а значение last_array равно [0, 8, 5].

Существует два вида постоянных массивов. Постоянный массив может быть либо частично или же от корки до корки настойчивый. Полностью постоянный массив может обновляться произвольное количество раз, в то время как частично постоянный массив может обновляться не более одного раза. В нашем предыдущем примере, если множество были лишь частично настойчивыми, созданиеother_array будет запрещено, однако создание последнего_массив все равно будет действительным. В самом деле, updated_array это массивотличный от множество и никогда не обновлялся до создания last_array.

Реализации

Существует множество реализаций постоянных массивов. В этом разделе положительное натуральное число п всегда будет размером постоянного массива.

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

Использование чисто функциональных структур данных

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

Использование массива и дерева модификаций

Полностью постоянный массив может быть реализован с использованием массива и так называемого трюка Бэкера.^[2] Эта реализация используется в OCaml модуль parray.ml^[3] Жан-Кристоф Филлиатр.

Чтобы определить эту реализацию, необходимо дать еще несколько определений. An начальный массив - это массив, который не создается обновлением другого массива. А ребенок массива ар массив формы ar.update (я, v), и ар это родительиз ar.update (я, v). А потомок массива ар либоар или потомок ребенка ар. В начальный массивмассива ар либо ар если ар является начальным, либо это начальный массив родительского элемента ар. То есть исходный массивар уникальный массив в этом такой, что ${\displaystyle \mathrm {ar} =init.update(i_{0},v_{0}).\dots .update(i_{m},v_{m})}$, с ар начальный и ${\displaystyle i_{0},\dots ,i_{m}}$ произвольная последовательность индексов и${\displaystyle v_{0},\dots ,v_{m}}$ произвольная последовательность значений. Асемья of array, таким образом, представляет собой набор массивов, содержащих начальный массив и всех его потомков. Наконец, дерево семейства массивов - это дерево чьи узлы являются массивами, а с ребром е из ар каждому своему ребенкуar.update (я, v).

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

Технически, учитывая два соседних массива ar1 и ar2, сar1 ближе к корню, чем ar2край от ar1 кar2 помечен (i, ar2 [i]), куда я единственная позиция, значение которой различается между ar1 и ar2.

Доступ к элементу я массива ар делается следующим образом. Еслиар это корень, тогда ar [i] равно корень [я]. В противном случае пустье край уходящий ар к корню. Если этикетка еявляется (я, v) тогда ar [i] равно v. В противном случае пусть ar2 это другой узел края е. потом ar [i] равноar2 [i]. Расчет ar2 [i] выполняется рекурсивно с использованием того же определения.

Создание ar.update (я, v) состоит в добавлении нового узлаar2 к дереву и краю е из ар к ar2 labelledby (я, v).

Наконец, перемещение корня в узел ар делается следующим образом. Еслиар уже рут, делать нечего. В противном случае пустье край уходящий ар к текущему корню, (я, v) itslabel и ar2 другой конец е. Перенос рута в ар выполняется путем перемещения корня в ar2, меняя метку ек (i, ar2 [i]), и изменение массив [я] к v.

Журнал-журнал-время

Существует реализация полностью постоянных массивов, так что поиск и обновления могут выполняться в${\displaystyle O(\log \log(\min(n,m))}$-время и место${\displaystyle O(m+n)}$, с м количество массивов и п количество элементов в массиве^[1]. Эта реализация оптимальна для поиска в соответствии с так называемой моделью «клетка-зонд».

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

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

1. Straka e, Милан (2013). Функциональные структуры данных и алгоритмы. Прага ,. С. 87–90.
2. Фийатр, Жан-Кристоф; Кончон, Сильвен (2007). Постоянная структура данных поиска союза (PDF). Нью-Йорк, Нью-Йорк, США: ACM. С. 37--46. ISBN  978-1-59593-676-9.
3. Филлиатр, Жан-Кристоф. "Реализация постоянного массива".

.