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

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

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

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

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

array = [0, 0, 0]
updated_array = array.update(0, 8)
other_array = array.update(1, 3)
last_array = updated_array.update(2, 5)

В конце выполнения значение массива по-прежнему равно [0, 0, 0]. значение обновленного_массива равно [8, 0, 0], значение другого_массива равно [0, 3, 0], а значение последнего_массива — [8, 0, 5].

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

Нижняя граница времени поиска постоянного массива

Учитывая, что непостоянные массивы поддерживают как обновления, так и поиск в постоянное время, естественно задаться вопросом, возможно ли то же самое с постоянными массивами. Следующая теорема показывает, что при мягких предположениях о пространственной сложности массива поиск должен занимать $\Omega (\log \log n)$ время в худшем случае, независимо от времени обновления, в модели ячейки-зонда .

Теорема ^[1]^: 67–69 — Рассмотрим частично постоянный массив с $n$ элементы и $m=n^{\gamma }$ модификации, где $\gamma$ это постоянное удовлетворение $1<\gamma \leq 2$ . Предполагая, что пространственная сложность массива равна $O(m\log ^{k}m)$ для постоянного $k$ , нижняя граница сложности поиска в этом частично постоянном массив $\Omega (\log \log n)$ .

Реализации

В этом разделе $n$ - количество элементов массива, а $m$ это количество обновлений.

Время журнала в худшем случае

Самая простая реализация полностью постоянного массива использует произвольную постоянную карту, ключами которой являются числа от 0 до n - 1. Постоянная карта может быть реализована с использованием постоянного сбалансированного дерева , и в этом случае как обновления, так и поиск будут занимать $O(\log n)$ время. Эта реализация оптимальна для модели указателя . ^[1]^: 88–89

Мелкий переплет

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

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

Постоянный массив, использующий трюк Бейкера, состоит из пары реальный массив, называемый массивом , и дерево массивов. Это дерево допускает произвольный корень — не обязательно исходный массив. корень можно переместить в произвольный узел дерева. Изменение корня путь от корня до произвольного узла 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[я] . Вычисление ar2[i] выполняется рекурсивно с использованием то же определение.

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

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

Обновления принимают $O(1)$ время. Поиски принимают $O(1)$ время, если корнем является просматриваемый массив, но $\Theta (m)$ время в худшем случае.

Ожидаемое амортизированное время записи журнала

В 1989 году Дитц ^[4] дал реализацию полностью постоянных массивов, используя $O(m+n)$ пространство, в котором можно осуществлять поиск $O(\log \log m)$ наихудшее время, и обновления могут быть выполнены в $O(\log \log m)$ ожидаемое амортизированное время. Согласно нижней границе из предыдущего раздела, эта временная сложность поиска оптимальна, когда $m=n^{\gamma }$ для $\gamma \in (1,2]$ . Эта реализация связана с проблемой поддержания порядка и включает в себя деревья vEB , по одному для всего массива и по одному для каждого индекса.

Straka показала, что время обеих операций можно (немного) сократить до $O(\log \log \min(m,n))$ . ^[1]^: 88–89

В худшем случае log-log-time

Страка показала, как добиться $O((\log \log m)^{2}/\log \log \log m)$ время наихудшего случая и линейное ( $O(m+n)$ ) пространство, или $O(\log \log m)$ наихудшее время и суперлинейное пространство. Остается открытым вопрос, возможно ли достичь наихудшего времени. $O(\log \log m)$ подчиняется линейному пространству. ^[1]^: 88

Ссылки

^ Перейти обратно: ^а ^б ^с ^д Страка э, Милан (2013). Функциональные структуры данных и алгоритмы . Прага. {{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка )
^ Филлятр, Жан-Кристоф; Коншон, Сильвен (2007). Постоянная структура данных для поиска объединений (PDF) . Нью-Йорк, штат Нью-Йорк, США: ACM. стр. 37–46. ISBN 978-1-59593-676-9 .
^ Филлиатр, Жан-Кристоф. «Реализация постоянного массива» . Гитхаб .
^ Дитц, Пол Ф. (1989). «Полностью постоянные массивы». Труды по алгоритмам и структурам данных . стр. 67–74. CiteSeerX 10.1.1.621.1599 . дои : 10.1007/3-540-51542-9_8 .

.

[Straka-1] Перейти обратно: ^а ^б ^с ^д Страка э, Милан (2013). Функциональные структуры данных и алгоритмы . Прага. {{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка )

[ML-2] Филлятр, Жан-Кристоф; Коншон, Сильвен (2007). Постоянная структура данных для поиска объединений (PDF) . Нью-Йорк, штат Нью-Йорк, США: ACM. стр. 37–46. ISBN 978-1-59593-676-9 .

[3] Филлиатр, Жан-Кристоф. «Реализация постоянного массива» . Гитхаб .

[Dietz-4] Дитц, Пол Ф. (1989). «Полностью постоянные массивы». Труды по алгоритмам и структурам данных . стр. 67–74. CiteSeerX 10.1.1.621.1599 . дои : 10.1007/3-540-51542-9_8 .

[1]

[2]

[3]

[4]