How can I have constant time initialization for multi-dimensional arrays?

Question

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:

SomeType array[N];

If 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 array, and order[k] is the order in which the array[k] was initialized. Note that none of array, place and order are initialized, their initial values are arbitrary. place[i] and 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 SomeType and N) overloading operator[].

Remark: This can clearly be extended to an array of such arrays.

Answer 1

It is amortized constant time, independent of the number of elements eventually used (initialized). But going to that complexity might just not be worth the time saved (if any).

A more practical way (due to Kernighan and Pike, IIRC) is to allocate an initial number of elements for a linear array, if you run out reallocate twice the number and initialize the new elements. The amortized cost is again constant for each initialized element, with less hassle. This obviosly works only for the case in which elements are added (mostly) sequentially; but if the elements are allocated haphazardly you'll probably be better off with another type of structure, like a hash table or some sort of tree.

Answer 2

I think you can use the same pattern, but simply need index conversion routines to go from multi-dimensional indices back to linear indices. For example, if you want a 2-D array, of dimensions A and B, create a linear array withN = A*B. Then array, place, and order would all have size N. When you access the 2-D array with indices a and b, instead compute n = a*B + b and lookup the linear array at n. This generalizes to as many dimensions as you wish.

tl;dr; A multidimensional array is a linear array, with a convenience interface.