In computer science, and more precisely regarding data structures, a persistent array is a persistent data structure with properties similar to a (non-persistent) 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 array
a r = [ e 0 , … , e n − 1 ] {\displaystyle \mathrm {ar} =[e_{0},\dots ,e_{n-1}]} is a data structure, with a fixed number n of elements e 0 , … , e n − 1 {\displaystyle e_{0},\dots ,e_{n-1}} . It is expected that, given the array ar and an index 0 ≤ i < n {\displaystyle 0\leq i<n} , the value e i {\displaystyle e_{i}} can be retrieved quickly. This operation is called a lookup. Furthermore, given the array ar, an index
0 ≤ i < n {\displaystyle 0\leq i<n} and a new value v, a new array ar2 with content [ e 0 , … , e i − 1 , v , e i + 1 , … , e n − 1 ] {\displaystyle [e_{0},\dots ,e_{i-1},v,e_{i+1},\dots ,e_{n-1}]} 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 = [0, 0, 0] updated_array = array.update(0, 8) other_array = array.update(1, 3) last_array = updated_array.update(2, 5)
At the end of execution, the value of array is still [0, 0, 0], the value of updated_array is [8, 0, 0], the value of other_array is [0, 3, 0], and the value of last_array is [8, 0, 5]. 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 Ω ( log log n ) {\displaystyle \Omega (\log \log n)} time in the worst case, regardless of update time, in the cell-probe model.
Implementations In this section, n {\displaystyle n} is the number of elements of the array, and m {\displaystyle m} 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 O ( log n ) {\displaystyle O(\log n)} time. This implementation is optimal for the pointer machine model.
Shallow binding A fully persistent array may be implemented using an array and the so-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(i,v), and ar is the parent of ar.update(i,v). 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 a r = i n i t . u p d a t e ( i 0 , v 0 ) . … . u p d a t e ( i m , v m ) {\displaystyle \mathrm {ar} =init.update(i_{0},v_{0}).\dots .update(i_{m},v_{m})} , with init initial and i 0 , … , i m {\displaystyle i_{0},\dots ,i_{m}} an arbitrary sequence of indexes and
… excerpt ends here. Continue reading the full article.
