The problem
We want to use a very large array for some computations. When created, all the elements of this array have to be initialized to some value. We'll only use a few values from the array1, so we don't want the runtime of the algorithm to be dominated by the initialization time.
In other words, we want to create and access an initialized array in constant time2.
How can this be done ? (Hint: we may use extra memory)
Solution
For a n-element array (
vec), we'll use two additional n-element arrays and a pointer3. The arrays are called from andto and the pointer is called top. init_val is the value we want to initialize the array with.- When an element
ifromvecis accessed, we'll know whether it has been initialized iffrom[i] < top and to[from[i]] = i. If this condition is satisfied, we returnvec[i]. Otherwise, we returninit_val. - Initially,
topis 0 - The array element
iis first accessed by the code:
from[i] = top to[top] = i vec[i] = init_val top++
Understanding the algorithm
Let's assume we want an array with size 10. This is the initial state of the array and helpers (
X denotes a memory location with arbitrary contents):vec: X X X X X X X X X X from: X X X X X X X X X X to: X X X X X X X X X X top: 0
Since
from and to contain unsigned values, the condition from[i] < top can never be true while top = 0. So all read accesses at this point will result in init_val.
Now suppose we write into the vector. Let's say
vec[4] <- 3. According to the algorithm, the next state will be:vec: X X X X 3 X X X X X from: X X X X 0 X X X X X to: 4 X X X X X X X X X top: 1
Now accesses to
i = 4 will satisfy the conditions from[4] = 0 < 1 and to[from[4]] = 4, so the value of vec[4] can be returned. Accesses to other indices will fail, because the only i that will pass the from[i] < top is an i for whichfrom[i] = 0, but only i = 4 will also fulfill the second condition to[from[i]] = i.
Let's work through another step. Let's say we write
vec[9] <- 6. The next state will be:vec: X X X X 3 X X X X 6 from: X X X X 0 X X X X 1 to: 4 9 X X X X X X X X top: 2
Again, the accesses to initialized indices,
i = 4, 9 will satisfy the conditions. Accesses to other indices will fail. Suppose for example an access to i = 7. Is from[7] < 2 ? Let's assume that by chance it is. It must be either 0 or 1 then. But for both, to points to the only really initialized fields, which are either 4 or 9, so the second condition will not be satisfied.
I hope it's now clear how
to, from and top interact to ensure that only initialized values will be actually returned. They kind-of close a loop - i points to from, from points to to and to points back to i. top makes sure that the location into was already initialized by the algorithm. Since the relevant locations in from and to are always in a controlled state, this algorithm can never be fooled by random values that were just lying around in the memory.
No comments:
Post a Comment