← Back to the algorithm list | Published on November 12th, 2022 |

When making a series of updates to something, you may wish to also retain a series of snapshots in between updates. For example, you may want to track version history for edits to a document. With limited storage space available, you cannot have a snapshot between every update. You would prefer to have a higher density of recent snapshots and a lower density of long-ago snapshots because it's typically more important to have higher granularity for more recent snapshots.

This algorithm is a simple way to keep a set of snapshots logarithmically-spaced back in history. It only ever keeps
around roughly `2 log`

snapshots for _{2}(n)`n`

updates, doesn't require any complex
bookkeeping, and runs in `O(1)`

time per update step.

** The algorithm:** After each step, add a new snapshot number

`n`

and delete the existing
snapshot number `n - (firstZeroBit(n) << d)`

where `firstZeroBit(x)`

returns the value
of the least significant zero bit of `x`

. The value `d`

is a customizable shift that
determines the density of snapshots. It can be set to any positive integer but has been set to 2 for the
visualization below. Here is a possible implementation of `firstZeroBit`

:
function firstZeroBit(x) { let bit = 1 while (bit && (x & bit) !== 0) bit <<= 1 return bit }

Here's a second possible (although less understandable) implementation of `firstZeroBit`

that uses bit
tricks and is equivalent to the first:

function firstZeroBit(x) { return (x + 1) & ~x }

The visualization below has one row for each step. Each successive row gains an additional column on the end to represent a new snapshot with the latest edits of the document. A given step has a snapshot when there is a solid square present for that step, and no longer has a snapshot when there is only a dot present for that step. The red-outlined squares represent snapshot deletes. At most one snapshot is deleted at each step. The number for each row is the number of snapshots retained (i.e. the number of remaining snapshots in that row), which is logarithmic in the number of steps.

Density:
`d = 2`