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

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

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

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

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

массив = [0, 0, 0] обновленный_массив = массив .update (0, 8) другой_массив = массив .update (1, 3)last_array = updated_array .update (2, 5)

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

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

Реализации [ править ]

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

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

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

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

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

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

Чтобы определить эту реализацию, необходимо дать еще несколько определений. Исходная матрица представляет собой массив , который не порождается обновления на другой массив. Ребенок из массива ар представляет собой массив вида ar.update (I, V) , и ар является родителем из ar.update (I, V) . Потомок из массива аг либо аг или потомок ребенка ар . Первоначальный массив из массива аг либо аг , если аг является начальным, или это исходный массив родителяар . То есть начальный массив ar является уникальным массивом init, таким, что с начальным ar и произвольной последовательностью индексов и произвольной последовательностью значений. Семьи массива, таким образом , набор массивов , содержащих исходный массив и всех его потомков. Наконец, дерево семейства массивов - это дерево , узлы которого являются массивами, и с ребром e от ar до каждого его дочернего элемента ar.update (i, 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}}$

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

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

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

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

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

Log-log-time [ править ]

В 1989 году Дитц ^[4] представил реализацию полностью постоянных массивов, так что поиск и обновления могут выполняться во времени и в пространстве , где m - количество массивов, а n - количество элементов в массиве. ^[1] Эта реализация оптимальна для поиска в соответствии с так называемой моделью «клетка-зонд».${\ Displaystyle О (\ журнал \ журнал (\ мин (п, м))}$${\ Displaystyle О (м + п)}$

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

Ссылки [ править ]

.