A fun lazy / incremental calculation helper

README.md

A short-ish example of incremental & lazy alternative to Array#reduce when you have a bunch of rapidly changing values.

The basic idea is to use a normal array and push values to it, but also think of the array as a representation of a binary tree (using the scheme outlined in Wikipedia). Each tree node keeps track of the reduced value of the subtree under it, and whenever something changes (i.e. a value is pushed to the array, a value is removed etc.) the changed node and its ancestors are marked to be "dirty", i.e. needing recalculation. All the dirty nodes get refreshed lazily when the reduced value for the tree is needed.

Each single tree modification marks at most 2 * log N nodes dirty (where N is the number of nodes in the tree). Therefore calculating the reduced value takes at O(min(m log N, N)) time (where m is the number of single modifications done to the tree since the last time the reduced value was calculated), assuming the given reduce operation takes a constant amount time.

The incrementalist.mjs file implements a class that takes two functions upon instantiation: a mapper and a reducer. The mapper returns the reduced value for a single node and the reducer combines two reduced (or mapped) values.

The usage.mjs file gives an example how the code could be used to keep track of multiple aggregates.

incrementalist.mjs

export class Incrementalist {
  constructor({ map, reduce }) {
    this._nodes = [];
    this._map = map;
    this._reduce = reduce;
  }

  reduce() {
    return rereduce(this._reduce, this._nodes, 0);
  }

  insert(value) {
    const nodes = this._nodes;
    const mapped = this._map(value);

    const node = {
      // `node` is initially pushed to the end of `nodes`, becoming a new leaf node in our tree.
      // `index` and `reduced` as the tree gets mutated.
      index: nodes.length,
      mapped: mapped,
      reduced: mapped,
      dirty: false,
      remove() {
        // Check that `node` hasn't already been removed.
        if (nodes.length <= node.index && nodes[node.index] !== node) {
          return;
        }

        // Remove the last node from `nodes` to take `node`'s place in the tree.
        // As the last element in `nodes` it has to be a leaf.
        // Mark the branch dirty.
        markDirty(nodes, nodes.length - 1);
        const leaf = nodes.pop();

        // If `node` happened to be the leaf we popped above then we're done.
        // Otherwise move `leaf` into `node`'s old place and mark the branch dirty.
        if (leaf !== node) {
          nodes[node.index] = leaf;
          leaf.index = node.index;
          markDirty(nodes, leaf.index);
        }
      },
    };

    nodes.push(node);
    markDirty(nodes, node.index);
    return node;
  }
}

// Mark a node AND its ancestors dirty.
// Note that we can bail out early on already-dirty ancestors.
function markDirty(nodes, index) {
  do {
    nodes[index].dirty = true;
    index = Math.floor((index - 1) / 2);
  } while (index >= 0 && !nodes[index].dirty);
}

// Calculate the reduced value of the subtree rooted on `index`.
// Only recompute stuff for dirty nodes, use cached values otherwise.
function rereduce(reduce, nodes, index) {
  if (index >= nodes.length) {
    return undefined;
  }

  const node = nodes[index];
  if (node.dirty) {
    node.reduced = node.mapped;

    const left = index * 2 + 1;
    if (left < nodes.length) {
      node.reduced = reduce(node.reduced, rereduce(reduce, nodes, left));
    }

    const right = left + 1;
    if (right < nodes.length) {
      node.reduced = reduce(node.reduced, rereduce(reduce, nodes, right));
    }

    node.dirty = false;
  }
  return node.reduced;
}

usage.mjs

import { Incrementalist } from "./incrementalist.mjs";

const inc = new Incrementalist({
  map: (value) => ({
    count: 1,
    sum: value,
    avg: value,
    min: value,
    max: value,
  }),
  reduce: (a, b) => ({
    count: a.count + b.count,
    sum: a.sum + b.sum,
    avg: (a.sum + b.sum) / (a.count + b.count),
    min: Math.min(a.min, b.min),
    max: Math.max(a.max, b.max),
  }),
});

// Initial population takes O(1) time per insert...
for (let i = 0; i < 100; i++) {
  inc.insert(Math.random());
}
// ...and the first reduce() takes O(N) time (N = the number of values in the tree).
console.log(inc.reduce());

// Subsequent insert(value) and remove() calls take O(log N) time...
let node = inc.insert(100000);
inc.insert(-100);
inc.insert(100);
node.remove();
// ...while reduce() calls take O(min(m log N, N)) time
// (m = the number of inserted / deleted values since the last reduce()).
console.log(inc.reduce());