Persistent array
In computer science, and more precisely regarding data structures, a persistent array is a persistent data structure with properties similar to a array. That is, after a value's update in a persistent array, there exist two persistent arrays: one persistent array in which the update is taken into account, and one which is equal to the array before the update.
Difference between persistent arrays and arrays
An arrayis a data structure,
with a fixed number n of elements. It is expected that, given the array ar and an
index, the value can be
retrieved quickly. This operation is called a
lookup. Furthermore, given the array ar, an index
and a new value v, a new array ar2 with
content can
be created quickly. This operation is called an update. The
main difference between persistent and non-persistent arrays being
that, in non-persistent arrays, the array ar is destroyed during
the creation of ar2.
For example, consider the following pseudocode.
array =
updated_array = array.update
other_array = array.update
last_array = updated_array.update
At the end of execution, the value of array is still , the
value of updated_array is , the value of other_array
is , and the value of last_array is .
There exist two kinds of persistent arrays. A persistent array may be
either partially or fully persistent. A fully persistent
array may be updated an arbitrary number of times while a partially
persistent array may be updated at most once. In our previous example,
if array were only partially persistent, the creation of
other_array would be forbidden; however, the creation of
last_array would still be valid. Indeed, updated_array is an array
distinct from array and has never been updated before the creation
of last_array.
Lower Bound on Persistent Array Lookup Time
Given that non-persistent arrays support both updates and lookups in constant time, it is natural to ask whether the same is possible with persistent arrays. The following theorem shows that under mild assumptions about the space complexity of the array, lookups must take time in the worst case, regardless of update time, in the cell-probe model.Implementations
In this section, is the number of elements of the array, and is the number of updates.Worst case log-time
The most straightforward implementation of a fully persistent array uses an arbitrary persistent map, whose keys are the numbers from 0 to n − 1. A persistent map may be implemented using a persistent balanced tree, in which case both updates and lookups would take time. This implementation is optimal for the pointer machine model.Shallow binding
A fully persistent array may be implemented using an array and theso-called Baker's trick. This implementation is used in the OCaml module parray.ml by Jean-Christophe Filliâtre.
In order to define this implementation, a few other definitions must
be given. An initial array is an array that is not generated by
an update on another array. A child of an array ar is an
array of the form ar.update, and ar is the parent
of ar.update. A descendant of an array ar is either
ar or the descendant of a child of ar. The initial array
of an array ar is either ar if ar is initial, or it is the
initial array of the parent of ar. That is, the initial array of
ar is the unique array init such that, with init initial
and an arbitrary sequence of indexes and
an arbitrary sequence of value. A
family of arrays is thus a set of arrays containing an initial
array and all of its descendants. Finally, the tree of a family of
arrays is the tree whose nodes are the
arrays, and with an edge e from ar to each of its children
ar.update.
A persistent array using Baker's trick consists of a pair with
an actual array called array and the tree of arrays. This tree
admits an arbitrary root - not necessarily the initial array. The
root may be moved to an arbitrary node of the tree. Changing the root
from root to an arbitrary node ar takes time proportional to
the depth of ar. That is, in the distance between root and
ar. Similarly, looking up a value takes time proportional to the
distance between the array and the root of its family. Thus, if the
same array ar may be lookup multiple times, it is more efficient
to move the root to ar before doing the lookup. Finally updating
an array only takes constant time.
Technically, given two adjacent arrays ar1 and ar2, with
ar1 closer to the root than ar2, the edge from ar1 to
ar2 is labelled by ', where i the only position
whose value differ between ar1 and ar2.
Accessing an element i of an array ar is done as follows. If
ar is the root, then ar equals root. Otherwise, let
e the edge leaving ar toward the root. If the label of e
is ' then ar equals v. Otherwise, let ar2 be
the other node of the edge e. Then ar equals
ar2. The computation of ar2 is done recursively using
the same definition.
The creation of ar.update consists in adding a new node
ar2 to the tree, and an edge e from ar to ar2 labelled
by '.
Finally, moving the root to a node ar is done as follows. If
ar is already the root, there is nothing to do. Otherwise, let
e the edge leaving ar toward the current root, ' its
label and ar2 the other end of e. Moving the root to ar is
done by first moving the root to ar2, changing the label of e
to , and changing array to v.
Updates take time. Lookups take time if the root is the array being looked up, but time in the worst case.
Expected amortized log-log-time
In 1989, Dietzgave an implementation of fully persistent arrays using space such that lookups can be done in worst-case time, and updates can be done in
expected amortized time. By the lower bound from the previous section, this time complexity for lookup is optimal when for. This implementation is related to the order-maintenance problem and involves vEB trees, one for the entire array and one for each index.
Straka showed that the times for both operations can be improved to.