# Initialize array in amortized constant time — what is this trick called?

There is this data structure that trades performance of array access against the need to iterate over it when clearing it. You keep a generation counter with each entry, and also a global generation counter. The "clear" operation increases the generation counter. On each access, you compare local vs. global generation counters; if they differ, the value is treated as "clean".

This has come up in this answer on Stack Overflow recently, but I don't remember if this trick has an official name. Does it?

One use case is Dijkstra's algorithm if only a tiny subset of the nodes has to be relaxed, and if this has to be done repeatedly.

-
Interesting trick, but it has quite an overhead. So I wonder which uses have clearing the array as such a common operation that the price pays of? (Sincere question!) – Joachim Sauer Jul 9 '12 at 20:52
@JoachimSauer: Edited. – krlmlr Jul 9 '12 at 21:02
Amortized?..... – user1249 Jul 9 '12 at 22:00
@Joachim: It's used to fast clear buffers for rendering- roughly. They just have a "clear bit" per 64kb or somesuch like that. – DeadMG Jul 9 '12 at 22:53
@user946850 "amortized" mean that you can prove that an expensive operation happens rarely enough in the overall picture that it does not contribute more than e.g. O(1) – user1249 Jul 9 '12 at 23:21

The aforementioned approach requires that each cell be able to hold a number large enough to hold the number of times the array may need to be reinitialized, which is a substantial space penalty. If a slot is capable of holding at least one value which will never be legitimately written, one may avoid having any other (non-constant) space penalty at the expense of adding an `O(Wlg(N))` time penalty, where `W` is the number of distinct array slots written between clearing operations and `N` is the size of the array. For example, suppose one will be storing integers from -2,147,483,647 to 2,147,483,647 (but never -2,147,483,648) and one wants blank array items to read as zero. Start by filling the array with -2,147,483,648 (call that value `B`). When reading an array slot for the application, report a value of `B` as zero. Before writing array slot `I`, check whether it held `B` and if so and `I` is greater than one, store a zero to slot `I/4` after performing a similar check for that location (and, if it held `B`, `I/16`, etc).

To clear the array, start with `I` equal to 0 or 1, depending upon the array base (the algorithm as described will work for either). Then repeat the following procedure: If item `I` is `B`, increment `I` and, if doing so yields a multiple of four, divide by four (terminate if the divide yields a value of 1); if item `I` is not `B`, store `B` there and multiply `I` by four (if `I` starts at zero, multiplying by four will leave it zero, but since item 0 will be blank, `I` will get incremented).

Note that one could replace the constant "four" above with other numbers, with larger values generally requiring less work tagging, but smaller values generally requiring less work clearing; since array slots that are tagged have to be cleared, a value of three or four is almost certainly optimal; since the value four is certainly close to optimal, is better than two or eight, and is more convenient than any other number, it would seem the most reasonable choice.

-
It is sufficient to have a version counter capable to accommodate enough sequential resets before all cells are updated with fresh values. In practice a byte might be enough, or even less in tighter loops. – 9000 Jul 11 '12 at 16:50
@9000: Code which relies upon such behavior is apt to be fragile, especially given that the only reason to use such a 'pseudo-clear' approach (as opposed to simply clearing the array) would be if the set of items that would need to be cleared was typically small and variable--a pair of conditions which conspire to increase the likelihood that an item might get used, "cleared", and then remain untouched for an arbitrarily long time. One could consider scanning the array and physically clearing any old slots when the counter is going to wrap, but... – supercat Jul 11 '12 at 17:23
...if the wrap value of the counter is constant, the average amount of work for each array clear operation would be O(N), with N being the size of the array. Not that such a thing might not be useful in practice, since an O(N) implementation which is sped up by a factor of 65,536 would still be O(N), but would also be 65,536 times as fast as the non-improved one. Incidentally, the cases where these approaches would be helpful may also benefit from using a sparse-array data structure, which could use O(AlgN) space to hold an array with an array of size N with A non-blank elements. – supercat Jul 11 '12 at 17:31

I would call it "lazy array cell reinitialization", but it doesn't seem to have any established name (that is, name being in wide use).

The algorithm is clever, but very specialized and applicable in a very narrow area.

-

I believe it is a special case of memoization, except in this case, the "memos" implicitly "age" with each increment of the global counter. I guess a kind of "backwards memoization'.

-