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$
6
  • $\begingroup$ @Aryabhata What is the reference you mentioned? $\endgroup$
    – uli
    Mar 19, 2012 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, 2012 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, 2012 at 13:36
  • $\begingroup$ @uli: This is a seeding question, I actually read this a long time back. $\endgroup$
    – Aryabhata
    Mar 19, 2012 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, 2012 at 15:56

1 Answer 1

16
$\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$
4
  • $\begingroup$ But isn't it possible that by chance $P[V[i]]$ equals $i$ without $A[i]$ having ever been set? $\endgroup$ Jun 30, 2013 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$
    – AturSams
    Mar 18, 2014 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, 2018 at 19:32
  • $\begingroup$ Just updating (sorry for the 8y difference though) that a new paper found a way to make the chaining (P[V[i]]==i) in-place, and thus only needing O(1) extra space. I wrote more about it in this Article. $\endgroup$
    – Tom
    Dec 8, 2020 at 17:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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