Choose K Implementations

JavaScript performance comparison

Test case created by jrwats

Preparation code


      
      <script>
Benchmark.prototype.setup = function() {
  let INPUT = 'abcdefghijklm';
  let K = 4;
  
  function visitK_stack(items, k, visit) {
    let stack = [];
    // Push singleton arrays of all top-level indices, 0..N-k
    for (let initIdx = items.length - k; initIdx >= 0; --initIdx) {
      stack.push([initIdx]);
    }
  
    while (stack.length) {
      let indices = stack.pop();
      if (indices.length === k) {
        visit(indices.map(i => items[i]));
      } else {
        let lastIdx = indices[indices.length - 1];
        for (let idx = items.length - 1; idx > lastIdx; --idx) {
          let next = indices.slice();
          next.push(idx);
          stack.push(next);
        }
      }
    }
  }
  
  function chooseK_stack(items, k) {
    let result = [];
    visitK_stack(items, k, e => result.push(e));
    return result;
  }
  
  
  // Just a dumb "state-holder" which presumably should have to pass
  // less on the stack ("this" reference vs 2 params)? I'll test that
  // theory, but it's probably overkill
  function State(items, k) {
    this.items = items;
    this.k = k;
  }
  
  // Alternative solution.  Instead of "leaf" calls returning base case
  // empty lists. We pass our aggregate array to which subcalls add
  // completed collections.  Tracking the stack of members along the way
  State.prototype.visitK = function(curIndices, visit) {
    if (curIndices.length === this.k) {
      // visit
      visit(curIndices.map(i => this.items[i], this));
    } else {
      let last = curIndices[curIndices.length - 1];
      for (let idx = last + 1; idx < this.items.length; ++idx) {
        curIndices.push(idx);
        this.visitK(curIndices, visit);
        curIndices.pop();
      }
    }
  }
  
  function chooseK_rec_state(items, k) {
    let result = [];
    let state = new State(items, k);
    for (let idx = 0; idx <= items.length - k; ++idx) {
      state.visitK([idx], e => result.push(e));
    }
    return result;
  }
  
  let visitK_rec = function(items, k, curIndices, visit) {
    if (curIndices.length === k) {
      // visit
      visit(curIndices.map(i => items[i]));
    } else {
      let last = curIndices[curIndices.length - 1];
      for (let idx = last + 1; idx < items.length; ++idx) {
        curIndices.push(idx);
        visitK_rec(items, k, curIndices, visit);
        curIndices.pop();
      }
    }
  }
  
  function chooseK_rec(items, k) {
    let result = [];
    for (let idx = 0; idx <= items.length - k; ++idx) {
      visitK_rec(items, k, [idx], e => result.push(e));
    }
    return result;
  }
  // (2) Add all the sublists of size k (without items[idx]),
  //   i.e. starting at idx + 1
  function _chooseK(items, idx, k) {
    if (k === 0) {
      return [[]];
    } else if (idx >= items.length) {
      return [];
    }
    return append(
      _chooseK(items, idx + 1, k - 1).map(
        (s) => append([items[idx]], s)
      ),
      _chooseK(items, idx + 1, k)
    );
  }
  
  // [].push.apply actually blows the callstack! Hand-roll it to "fight
  // fair" with other implementations.  (The built-in
  // Array.prototype.concat is expensive)
  function append(res, more) {
    for (let ii = 0; ii < more.length; ++ii) {
      res.push(more[ii]);
    }
    return res;
  }
  
  let simpleChooseK = (items, k) => _chooseK(items, 0, k);
  
  
  function visitKIter(items, k, visit) {
    // Array(k).fill(0).map((_,i) => i);
    let indices = Array(k);
    for (let i = 0; i < k; ++i) {
      indices[i] = i;
    }
    do {
      visit(indices.map(i => items[i]));
    } while (increment(indices, items.length));
  }
  
  // Increment the indices representing a combination (all unique and
  // monotoonically increasing) by 1
  function increment(indices, max) {
    const k = indices.length;
  
    // A micro-optimization as this is the "hot loop" (least significant "digit")
    if (++indices[k - 1] <= max - 1) {
      return true;
    }
    for (var i = k - 2; ++indices[i] > max - (k - i); --i);
    if (i < 0) {
      return false;
    }
    let val = indices[i];
    for (let j = i + 1; j < k; ++j) {
      indices[j] = ++val;
    }
    return true;
  }
  
  function chooseKIter(items, k) {
    let result = [];
    visitKIter(items, k, e => result.push(e));
    return result;
  }
  
  

};
</script>

Test runner

Warning! For accurate results, please disable Firebug before running the tests. (Why?)

Java applet disabled.

Testing in CCBot 2.0.0 / Other 0.0.0
Test Ops/sec
No-visit recursive
simpleChooseK(INPUT, K);
pending…
iterative "stack" visitor
chooseK_stack(INPUT, K);
pending…
Iterative "incrementing" indices
chooseKIter(INPUT, K);
pending…
recursive visitor
chooseK_rec(INPUT, K);
pending…
recursive visitor (class)
chooseK_rec_state(INPUT, K);
pending…

Compare results of other browsers

Revisions

You can edit these tests or add even more tests to this page by appending /edit to the URL.

0 Comments