19
$\begingroup$

I recently read that it is possible to have arrays which need not be initialized, i.e. it is possible to use them without having to spend any time trying to set each member to the default value. i.e. you can start using the array as if it has been initialized by the default value without having to initialize it. (Sorry, I don't remember where I read this).

For example as to why that can be surprising:

Say you are trying to model a worst case $\mathcal{O}(1)$ hashtable (for each of insert/delete/search) of integers in the range $[1, n^2]$.

You can allocate an array of size $n^2$ bits and use individual bits to represent the existence of an integer in the hashtable. Note: allocating memory is considered $\mathcal{O}(1)$ time.

Now, if you did not have to initialize this array at all, any sequence of say $n$ operations on this hashtable is now worst case $\mathcal{O}(n)$.

So in effect, you have a "perfect" hash implementation, which for a sequence of $n$ operations uses $\Theta(n^2)$ space, but runs in $\mathcal{O}(n)$ time!

Normally one would expect your runtime to be at least as bad as your space usage!

Note: The example above might be used for an implementation of a sparse set or sparse matrix, so it is not only of theoretical interest, I suppose.

So the question is:

How is it possible to have an array like data-structure which allows us to skip the initialization step?

$\endgroup$
  • $\begingroup$ @Aryabhata What is the reference you mentioned? $\endgroup$ – uli Mar 19 '12 at 8:47
  • 1
    $\begingroup$ "using memory" is not the same as "having allocated but never accessed memory", therefore I think the motivating "paradox" is not quite existent. $\endgroup$ – Raphael Mar 19 '12 at 8:54
  • 1
    $\begingroup$ I think the first paragraph is pretty clear: have a default value, without actually taking time to fill the array with the default value. The answer, in case someone else has time to write it up before I do, is here scholar.google.co.uk/… There's also a very brief explanation on my blog rgrig.blogspot.co.uk/2008/12/array-puzzle-solution.html $\endgroup$ – rgrig Mar 19 '12 at 13:36
  • $\begingroup$ @uli: This is a seeding question, I actually read this a long time back. $\endgroup$ – Aryabhata Mar 19 '12 at 15:56
  • $\begingroup$ @Raphael: It is still surprising when you hear about such a thing the first time. Most of the paradoxes aren't :-) $\endgroup$ – Aryabhata Mar 19 '12 at 15:56
15
$\begingroup$

This is a very general trick, which can be used for other purposes than hashing. Below I give an implementation (in pseudo-code).

Let three uninitialized vectors $A$, $P$ and $V$ of size $n$ each. We will use these to do the operations requested by our data structure. We also maintain a variable $pos$. The operations are implemented as following:

init:
  pos <- 0

set(i,x):
if not(V[i] < pos and P[V[i]] = i) 
  V[i] <- pos, P[pos] <- i, pos <- pos + 1
A[i] <- x

get(i):
if (V[i] < pos and P[V[i]] = i) 
  return A[i] 
else 
  return empty 

The array $A$ simply stores the values that are passed through the $set$ procedure. The arrays $V$ and $P$ work as certificates that can tell if a given position in $A$ has been initialized.

Note that at every moment the elements in $P$ ranging from $0$ to $pos-1$ are initialized. We can therefore safely use these values as a certificate for the initialized values in $A$. For every position $i$ in $A$ that is initialized, there is a corresponding element in the vector $P$ whose value is equal to $i$. This is pointed by $V[i]$. Therefore, if we look at the corresponding element, $P[V[i]]$ and its value is $i$, we know that $A[i]$ has been initialized (since $P$ never lies, because all the elements that we're considering are initialized). Similarly, if $A[i]$ is not initialized, then $V[i]$ may point either to a position in $P$ outside the range $0..pos-1$, when we know for sure that it's not initialized, or may point to a position within that range. But this particular $P[j]$ corresponds to a different position in $A$, and therefore $P[j] \neq i$, so we know that $A[i]$ has not been initialized.

It's easy to see that all these operations are done in constant time. Also, the space used is $O(n)$ for each of the vectors, and $O(1)$ for the variable $pos$, therefore $O(n)$ in total.

$\endgroup$
  • $\begingroup$ But isn't it possible that by chance $P[V[i]]$ equals $i$ without $A[i]$ having ever been set? $\endgroup$ – Robert S. Barnes Jun 30 '13 at 8:10
  • $\begingroup$ It is but then pos will be smaller than V[i] now wouldn't it? Cause otherwise it wouldn't be by chance. Since by having pos higher than V[i], it means we have specifically set the value of P at index V[i] to a specific value we chose, namely i. $\endgroup$ – wolfdawn Mar 18 '14 at 18:34
  • $\begingroup$ Note that this is a classic example of something that is impossible to do in (portable) C. $\endgroup$ – TLW Oct 7 '18 at 19:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.