For a regular array, I understand that if we have the tradeoff of space vs time, and we use more space to implement a Which, Data, and When pointers to the actual array, we can initialize the array in constant time because there are pointers to access and keep track of the elements in the array.
How can I extend the idea of using the Which, Data, and When pointers to have constant time initialization for multi-dimensional arrays? Would I have to have multiple Which, Data, and When pointers to keep track of n-th D array dimensions?
Or is the use of hierarchical tables, which stores multi-dimensional arrays as an array of pointers to tables, where each table contains a row of the array, and implementing the Which, Data, and When pointers to the hierarchical tables a correct way for having constant time initialization of multi-dimensional arrays?
Edit: Use C notation for simplicity. Let's say for a large
N we have an array:
N is very large, and only a few of the array's elements are ever used, just initializing it can become the largest cost of an algorithm. A way around this is to have a self-checking structure that can be filled in on demand. To the above add (I'm not the original poster, so I will use my own names here):
int last_used = -1, place[N], order[N];
The idea is that
last_used tells the last used entry,
place[i] is the index of the
i-th asigned element of
order[k] is the order in which the
array[k] was initialized. Note that none of
order are initialized, their initial values are arbitrary.
order[k] serve to check each other. To use
array[i], see if
order[i] < last_used (it is in the right range, might have been set already; if not, it is clearly garbage) and also
place[order[i]] == i. If so, the element has been used, go ahead. If not, do:
last_used++; /* Another one is in use */ place[last_used] = i; /* The next one in use is array[i] */ order[i] = last_used; /* Point back */ initialize(array[i]); /* Prepare for use */ /* Furiously frob array[i] */
The time of this is bounded by a constant; so the initialization time, amortized over the initialized elements, is constant. For a practical implementation, this can be packaged conveniently in a C++ class (templated on
Remark: This can clearly be extended to an array of such arrays.