Cartesian Product algo Benchmark

cartesian-product.benchmark.js

const Benchmark = require('benchmark');
const suite = new Benchmark.Suite();

const A = Array(3).fill(null).map((_, index) => index + 1);
const B = A.map((a) => [a, a * -1]);

suite
  .add('cartesianProduct_gen', function () { for (const _ of cartesianProduct_gen(B.slice())) { } })
  .add('cartesianProduct_loop', function () { for (const _ of cartesianProduct_loop(...B.slice())) { } })
  .add('cartesianProduct_genLoop', function () { for (const _ of cartesianProduct_genLoop(B.slice())) { } })
  .add('cartesianProduct_rsp', function () { for (const _ of cartesianProduct_rsp(...B.slice())) { } })
  .add('cartesianProduct_sebnukem', function () { for (const _ of cartesianProduct_sebnukem(B.slice())) { } })
  // add listeners
  .on('cycle', function (event) { console.log(String(event.target)); })
  .on('complete', function () { console.log('Fastest is ' + this.filter('fastest').map('name')); })
  // run async
  .run({ 'async': true });

function* cartesianProduct_gen(elements) {
  if (!elements.length) {
    return;
  }

  const end = elements.length - 1;

  function* appendMore(acc, start) {
    const head = elements[start];
    const hasReachedEnd = start === end;

    for (const it of head) {
      const accCopy = acc.slice().concat(it);

      if (hasReachedEnd) {
        yield accCopy;
      } else {
        yield* appendMore(accCopy, start + 1);
      }
    }
  }

  yield* appendMore([], 0);
}

function cartesianProduct_loop() {
  const N = arguments.length;

  var arr_lengths = Array(N);
  var digits = Array(N);
  var num_tot = 1;

  for (var i = 0; i < N; ++i) {
    const len = arguments[i].length;
    if (!len) {
      num_tot = 0;
      break;
    }
    digits[i] = 0;
    num_tot *= (arr_lengths[i] = len);
  }

  var ret = Array(num_tot);

  for (var num = 0; num < num_tot; ++num) {
    var item = Array(N);
    for (var j = 0; j < N; ++j) { item[j] = arguments[j][digits[j]]; }
    ret[num] = item;

    for (var idx = 0; idx < N; ++idx) {
      if (digits[idx] == arr_lengths[idx] - 1) {
        digits[idx] = 0;
      } else {
        digits[idx] += 1;
        break;
      }
    }
  }

  return ret;
}

function* cartesianProduct_genLoop(aListOfList) {
  const outputSize = aListOfList.length;
  const indexes = Array(outputSize).fill(0);

  while (true) {
    // Emit
    yield indexes.map((a, index) => aListOfList[index][a]);

    // Update indexes
    let j = indexes.length - 1;
    while (true) {
      indexes[j] += 1;
      if (indexes[j] < aListOfList[j].length) {
        break;
      }
      indexes[j] = 0;
      j -= 1;
      if (j < 0) {
        return;
      }
    }
  }
}

const _f = (a, b) => [].concat(...a.map(d => b.map(e => [].concat(d, e))));
const cartesianProduct_rsp = (a, b, ...c) => b ? cartesianProduct_rsp(_f(a, b), ...c) : a;

function cartesianProduct_sebnukem(a) {
  var i, j, l, m, a1, o = [];
  if (!a || a.length == 0) return a;

  a1 = a.splice(0, 1)[0];
  a = cartesianProduct_sebnukem(a);

  for (i = 0, l = a1.length; i < l; i++) {
    if (a && a.length) for (j = 0, m = a.length; j < m; j++)
      o.push([a1[i]].concat(a[j]));
    else
      o.push([a1[i]]);
  }

  return o;
}

cartesianProduct_gen x 148 ops/sec ±0.51% (82 runs sampled)
cartesianProduct_loop x 8,215,442 ops/sec ±0.59% (95 runs sampled)
cartesianProduct_rsp x 52,443,959 ops/sec ±0.81% (92 runs sampled)
cartesianProduct_sebnukem x 88,812,242 ops/sec ±1.11% (92 runs sampled)
Fastest is cartesianProduct_sebnukem