Персистентный массив

Определение:

{{{definition}}}

Интерфейс

• [X] статический конструктор, который принимает элемент X и возвращает массив, который содержит X в качестве его единственного элемента.
• LENGTH [A] возвращает длину массива A.
• ε является пустым массивом, иногда также обозначается []
• A [i] принимает массив A = [a₀, ..., an-1] и индекс i = 0..n-1, затем возвращает a_i.
• CONCATENATE(A,B) конкатентирует два массива: if A = [a₀,...,a_n-1] and B = [b₀,...,b_m-1], n,m ≥ 0, результат будет [a₀,...,a_n−1,"b"₀,...,b_m-1]. Часто записывается как A · B вместо CONCATENATE(A,B).
• HEAD(A,i) принимает на вход массив A = [a₀,...,an−1] и производный int, возвращает массив [a0,...,amin(i−1,n−1) ]. Если i < 0 результатом будет [].
• TAIL(A,i) принимает на вход массив A = ["a"₀,...,an−1] и производный int, возвращает массив [amax(i,0) ,...,an−1]. Если i ≥ n, результатом будет [].
• B - структура, то seq (B) обозначает строку, которая представлена B.

Основываясь на вышеприведенных операциях, ADT может быть расширен следующими операциями:

• [x0,..., xn−1] является сокращением для CONCATENATE([x0],CONCATENATE([x1],CONCATENATE(...,CONCATENATE([xn−2],[xn−1])))) . Обратите внимание, что в программе оценка этого выражения всегда включает n-2 конкатенации.
• REVERSE[A] принимает на вход массив A = [a0,...,a_n-1] и возвращает [a_n-1,...,a0].
• REPLACE[A,i, x] принимает на вход массив A = [a0,...,a_n-1], индекс i = 0..n − 1, и новый элемент x, выводит [a₀,...,a_i-1, x,a_i+1,...,a_n-1].
• A[i] ← x является сокращенным обозначением A ← REPLACE(A,i, x).
• INSERT[A,i, x] получает массив A = [a0,...,a_n-1], индекс i = 0..n−1, и новый элемент x и возвращает массив [a0,...,a_i-1, x,ai ,...,an−1] = HEAD(A,i) · [x] · TAIL(A,i), длина которого n-1.
• LEFTPART(A): возвращает (non-deterministically) массив, представляющий последовательность префикса A.
• RIGHTPART(A): возвращает (non-deterministically) массив, представляющий последовательность суффикса A.

Реализация персистентных массивом в виде сбалансированных деревьев

Будем использовать сбалансированные деревья в качестве нашей стандартной реализации постоянных массивов. (Реализации сбалансированных деревьев, таких как AVL-деревья и B-деревья, можно найти в соответствующих разделах сайта) Решающим моментом является то, что мы допускаем множественные ссылки на одно и то же поддерево: хотя концептуальное представление постоянных массивов - ориентированные деревья, их представление в памяти различно. Мы допускаем, что узел может быть преемником многих разных узлов.

{Определение |def= Пусть X - некоторое множество. Бинарное дерево с несколькими ссылками по X является кортежем B = (N, L, R) с L∩R = 0 /, L, R ⊆ N × N, таким, что

• (N, L∪R) является корневым ациклическим ориентированным графом с узлами N, ребрами L∪R.
• В каждом из двух подграфов (N, L) и (N, R) каждый узел имеет не более одного прямого преемника .
• Узлы без каких-либо преемников (листья B) должны быть все элементами X.

} Дано двоичное дерево с несколькими ссылками B = (N,L,R) и узел p ∈ N. Пишут LEFT(p) = q, если q является единственным приемником p в(N,L) и, если такого q не существует, пишем LEFT(p)= ⊥, предполагая, что ⊥ не содержит N. Аналогично, пишут RIGHT(p) = q, если q является единственным приемником p в(N,R) и, если такого q не существует, пишем RIGHT(p)= ⊥. Мы будем называть LEFT (p) левым дочерним элементом p и RIGHT (p) правым дочерним элементом. В B = (N, L∪R) узел p ∈ N может иметь много прямых предшественников q. Тогда ребра (q, p) ∈ E называют ссылками от q до p.

С каждым узлом p ∈ N мы можем идентифицировать строку seq (p) ∈ X *: Если p - лист, то согласно определению выше, p ∈ X. Мы можем установить seq (p) = x (строка, содержащая только x). Поскольку (N, L∪R ) ациклично, для всех внутренних узлов мы можем рекурсивно определить p ∈ N seq (p) = seq (LEFT (p)) seq (RIGHT (p)), задав seq (⊥) = ε. Наконец, пусть r - корень B. Тогда определимseq (B): = seq (r). В качестве примера, см. рисунок 1.2. В нашей реализации мы поддерживаем с каждым узлом p ∈ N длину seq (LEFT (p)). Это позволяет получить i-й символ строки seq (B), пройдя путь от корня до соответствующего листа. Мы также поддерживаем значение HEIGHT (p) для каждого p ∈ N, которое определяется как максимальная длина пути от p до листа в q ∈ N. Согласно этому определению все листья имеют высоту 0 и если мы устанавливаем HEIGHT (⊥) = -1, то HEIGHT(p) = max(HEIGHT(LEFT(p)), HEIGHT(RIGHT(p)))+1 для всех p ∈ N. Чтобы сбалансировать структуру, мы используем AVL-условие для двоичных деревьев. Def3 Бинарное дерево B = (N, L, R) является AVL-деревом, если оно удовлетворяет условию AVL, то есть для каждого p ∈ N |HEIGHT(LEFT(p))− HEIGHT(RIGHT(p))| ≤ 1. 1.2 конкатенация постоянных массивов, представленных в виде двоичных деревьев Для полноты мы покажем операции для конкатенации · и расщепления (HEAD и TAIL), которые особенно просты в реализации, запускаются во времени O (HEIGHT (r)) и позволяют нам реализовать полный интерфейс персистентного массива ADT. Для конкатенации см. Алгоритм 1.2.

NODE (l, r) является конструктором, который выдает созданный узел p с LEFT (p) = l и RIGHT (p) = r. Конструктор также определяет правильные значения p для HEIGHT (p) и LENGTH (p).

Обратите внимание, что время его работы равно O (| HEIGHT (r) -HEIGHT (l) |). Далее мы покажем алгоритм HEAD, алгоритм для TAIL является симметричным. 1.3 Разделение персистентного массива, представленного как двоичное дерево. Учитывая корневой узел r высоты h и целое число i, алгоритм 1.3 свяжет не более чем h + 1 двоичных дерева. Стоимость одной конкатенации пропорциональна разнице высот.

При использовании RAW с ограниченным размером арифметических операций, ADT для персистентных массивов могут быть реализованы таким образом, чтобы каждая из его операций выполнялась во времени O (logn).Если длины массивов представляются внутри границ слова. В противном случае временная граница O (min ((log n)2, k2)). Здесь n - максимальная длина задействованных массивов, а k – число, которые были использованы для создания массивов операндов.

Литература

• [Nobuhiro Izumi Hui-Hsiung "Acta Applicandae Texematicae",79–87.Bell numbers, log-concavity, and log-convexity 2000]
• [Aitken A. C. Edinburgh Texematical Notes,18–23 A problem in combinations 1933]
• [H. W.BeckerJohn Riordan "The arithmetic of Bell and Stirling numbers" American Journal of Texematics,1948,385–394]
• [E. T.Bell Exponential polynomials,Annals of Texematics,1934, 258–277]
• [E. T.Bell The iterated exponential integers,Annals of Texematics,1938,539–557]
• Bender Edward A.Williamson, S. Gill, Set Partitions, 319–320, 2006
• Bell numbers

Примeчания

--MikeTerentyev 16:07, 8 октября 2017 (MSK)MikeTerentyev