I am a bit unclear about the solution on how it is reducing initialization
time, can someone help? The only + i get is we are not initializing all
elements together but only when the element is accessed. This is addition
of two checks from[i]<top && to[from[i]]=i;
Also, what is the meaning of the names to and from here. The solution can
easily be forgotton unless the name significance is understood.
Question
One problem with trading more space to use less time is that initializing
the space can itself take a great deal of time. Show how to circumvent this
problem by designing a technique to initialize an entry of a vector to zero
the first time it is accessed. Your scheme should use constant time for
initialization and for each vector access, and use extra space proportional
to the size of the vector. Because this method reduces initialization time
by using even more space, it should be considered only when space is cheap,
time is dear and the vector is sparse.
Solution
The effect of initializing the vector *data*[0..*n*-1] can be accomplished
with a signature contained in two additional *n*-element vectors, *from*and
*to*, and an integer *top*. If the element *data*[*i*] has been
initialized, then *from*[*i*] < *top* and *to*[*from*[*i*]]=*i*. Thus
*from*is a simple signature, and
*to* and *top* together make sure that *from* is not accidentally signed by
the random contents of memory. Blank entries of *data* are uninitialized in
this picture:
[image: Initialization Structure]
The variable *top* is initially zero; the array element *i* is first
accessed by the code
from[i] = top
to[top] = i
data[i] = 0
top++
Best Regards
Ashish Goel
"Think positive and find fuel in failure"
+919985813081
+919966006652
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
