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

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

Мы называем ADT полностью персистентными(англ. fully persistent), если, помимо интерфейса, все операции сохраняют операнды неизменными, таким образом, что операнды и результаты таких операций могут быть свободно используемы повторно во время дальнейшего хода вычислений. Мы называем структуру данных (как реализацию абстрактного типа данных англ.ATD) полностью персистентной, если она эффективно реализует все операции предполагаемого, полностью персистентного ADT.

Интерфейс

• [math] [ X ][/math] статический конструктор, который принимает элемент [math] X [/math] и возвращает массив, который содержит [math] X [/math] в качестве его единственного элемента.
• [math] LENGTH [A] [/math] возвращает длину массива [math] A [/math].
• [math] \varepsilon [/math] является пустым массивом, иногда также обозначается [math] [ ][/math]
• [math] A [i] [/math] принимает массив [math] A = [a_0, ..., a_{n-1} ] [/math] и индекс [math] i = 0..n - 1 [/math] , затем возвращает [math] a_i [/math].
• [math] CONCATENATE(A,B) [/math] конкатентирует два массива: если [math] A = [a_0,..., a_{n-1} ] [/math] и [math] B = [b_0,..., b_{m-1} ]; n, m \geq 0[/math] , результат будет [math] [a_0 ,..., a_{n−1}, b_0,..., b_{m-1}] [/math] . Часто записывается как [math] A • B[/math] вместо [math] CONCATENATE (A,B) [/math] .
• [math] HEAD (A,i) [/math] принимает на вход массив [math] A = [a_0,...,a_{n−1}] [/math] и производный [math] int[/math] , возвращает массив [math] [a_0,...,a_{min(i−1,n−1)} ] [/math] . Если [math] i \lt 0[/math] результатом будет [math] [ ][/math] .
• [math] TAIL (A,i) [/math] принимает на вход массив [math] A = [a_0,...,a_n−1] [/math] и производный [math] int[/math] , возвращает массив [math] [a_{max(i,0)} ,...,a_{n−1}][/math] . Если [math] i \geq n[/math] , результатом будет [math] [ ][/math] .
• Если [math] B[/math] - структура, то [math] seq (B) [/math] обозначает строку, которая представлена [math] B[/math] .

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

• [math] [x0,..., x_{n−1}][/math] является сокращением для [math] CONCATENATE ([x_0], CONCATENATE ([x_1],CONCATENATE(...,CONCATENATE([x_{n−2}],[x_{n−1}])))) [/math] . Обратите внимание, что в программе оценка этого выражения всегда включает [math] n-2[/math] конкатенации.
• [math] REVERSE[A] [/math] принимает на вход массив [math] A = [a_0,...,a_{n-1}] [/math] и возвращает [math] [a_{n-1},...,a_0] [/math] .
• [math] REPLACE [A,i, x] [/math] принимает на вход массив [math] A = [a_0,...,a_{n-1}][/math] , индекс [math] i = 0.. n - 1 [/math] , и новый элемент [math] x[/math] , выводит [math] [a_0,...,a_{i-1}, x,a_{i+1},...,a_{n-1}][/math] .
• [math] A[i] \leftarrow x [/math] является сокращенным обозначением [math] A \leftarrow REPLACE(A,i, x)[/math] .
• [math] INSERT[A,i, x][/math] получает массив [math] A = [a_0,...,a_{n-1}][/math] , индекс [math] i = 0..n - 1 [/math] , и новый элемент [math] x [/math] и возвращает массив [math] [a_0,...,a_{i-1}, x,a_i ,...,a_{n−1}] = HEAD(A,i) [x] • TAIL(A,i) [/math] , длина которого [math] n-1[/math] .
• [math] LEFTPART (A) [/math] возвращает массив, представляющий последовательность префикса [math] A[/math] .
• [math] RIGHTPART(A) [/math] возвращает массив, представляющий последовательность суффикса [math] A[/math] .

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

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

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

Пусть [math] X[/math] - некоторое множество. Бинарное дерево с несколькими ссылками на [math] X[/math] является кортежем [math] B = (N, L, R) с L \cap R = 0 /, L, R \subseteq N × N[/math] , таким, что [math] (N, L \cup R)[/math] является корневым ациклическим ориентированным графом с узлами [math] N[/math] , ребрами [math] L \cup R[/math] . В каждом из двух подграфов [math] (N, L) и (N, R)[/math] каждый узел имеет не более одного прямого преемника . Узлы без каких-либо преемников (листья B) должны быть все элементами [math] X[/math] .

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

С каждым узлом [math] p \in N[/math] мы можем идентифицировать строку [math] seq (p) \in X [/math]  :

Если p - лист, то согласно определению выше, [math]  p \in X[/math] . Мы можем установить  [math] seq (p) = x[/math]  (строка, содержащая только x). Поскольку  [math] (N, L \cup R )[/math]  ациклично, для всех внутренних узлов мы можем рекурсивно определить  [math] p \in N  seq (p) = seq (LEFT (p)) seq (RIGHT (p))[/math] , задав  [math] seq (\perp) = ε \lt tex\gt  . Наконец, пусть r - корень B. Тогда определимseq (B): = seq (r). В качестве примера, см. рисунок 1.2.
В нашей реализации мы поддерживаем с каждым узлом  \lt tex\gt  p \in N[/math]  длину  [math] seq (LEFT (p))[/math] . Это позволяет получить
[math] i-й[/math]  символ строки  [math] seq (B)[/math] , пройдя путь от корня до соответствующего листа. Мы также поддерживаем значение HEIGHT (p) для каждого  [math] p \in N[/math] , которое определяется как максимальная

длина пути от p до листа в [math] q \in N[/math] . Согласно этому определению все листья имеют высоту [math] 0[/math] и если мы устанавливаем [math] HEIGHT (\perp) = -1[/math] , то [math] HEIGHT(p) = max(HEIGHT(LEFT(p)), HEIGHT(RIGHT(p)))+1[/math] . для всех [math] .p \in N[/math] .. Чтобы сбалансировать структуру, мы используем AVL-условие для двоичных деревьев. Def3 Бинарное дерево [math] B = (N, L, R) [/math] является AVL-деревом, если оно удовлетворяет условию AVL, то есть для каждого [math] p \in N |HEIGHT(LEFT(p))− HEIGHT(RIGHT(p))| \le 1[/math] . 1.2 конкатенация постоянных массивов, представленных в виде двоичных деревьев Для полноты мы покажем операции для конкатенации • и расщепления [math] (HEAD и TAIL) [/math] , которые особенно просты в реализации, запускаются во времени [math] O (HEIGHT (r)) [/math] и позволяют нам реализовать полный интерфейс персистентного массива ADT. Для конкатенации см. Алгоритм 1.2.

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

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

При использовании 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