This is an old, clever way of storing a set of all indices such that
both "add element" and "membership test" operations can be performed
in constant time. I think it first appeared in graph algorithms where
it a avoids the cost of initializing an adjacency matrix, which is
very handy for a big graph!
You can use it for other algorithms where you have sets of small
integers that only grow, never contract.
With this algorithm, assigning a value to array A, A[i] = x becomes
if (i is not already member indices of A that have been set)
Add i to the set
A[i] = x
and accessing an array element "return A[i]" becomes
if (i is a member of the set of indices of A elements that have been
set)
return A[i]
else
return default value
The default value is whatever you _would_ have initialized A with if
you were allowed O(n) time to do it.
As you say, the names from, to, and top are not are not so helpful..
Here's the best I can do:
Top is the number of elements in the set. "To" is a list of elements
in the set stored in arbitrary order. "From" is a map that takes i to
the location in To where i is stored.
So I would change their names to n_elts, set, and map. Both of the
arrays contain junk when n_elts is zero. As indices are added, set is
filled in order 0,1,2,...n-1 and map is filled in the same order as
A's elements are set.
I might code the membership test like this:
boolean isMember(int i)
{
int locationInSet = map[i];
// Check to see if the location has even a chance of being valid.
if (locationInSet < 0 || locationInSet >= n_elts)
return false;
// It might be valid, but it could still be junk. We need to see if
i is in the set.
if (set[locationInSet] == i)
return true;
// It was junk.
return false;
}
To add a member that you already know is not in the set:
void addMember(int i)
{
// Put i in the set at a fresh location.
set[n_elts] = i;
// Update the map to point to this location.
map[i] = n_elts;
// Show that we have a new set member.
++n_elts;
}
On May 14, 8:18 pm, Ashish Goel <[email protected]> wrote:
> 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 [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
