13

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.

Improve this question
8
  • 2
    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, 2012 at 20:52
  • @JoachimSauer: Edited.
    – krlmlr
    Jul 9, 2012 at 21:02
  • Sounds very expensive in the general case for both memory usage and accesses cost. The use case for this technique must be very specific.
    – Martin York
    Jul 9, 2012 at 21:52
  • 3
    @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, 2012 at 22:53
  • 3
    @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, 2012 at 23:21

3 Answers 3

Reset to default
2

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.

Improve this answer
3
  • 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, 2012 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, 2012 at 17:23
  • 1
    ...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, 2012 at 17:31
1

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.

Improve this answer
1

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'.

Improve this answer

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.