Subset Sum Problem

alg1.js

subsetSumExact = (function () {
  'use strict';

  // This allows conveniet access to array of bits
  // with indices in the range [min, max].
  function BitSet(min, max, arr) {
    var size = max - min + 1;
    var data = arr || new Uint32Array(Math.ceil(size/32));

    this.set = function (i) {
      i -= min;
      data[Math.floor(i/32)] |= 1 << (i % 32);
    }

    this.isSet = function (i) {
      i -= min;
      return !!(data[Math.floor(i/32)] & (1 << (i % 32)));
    }

    this.copy = function (i) {
      return new BitSet(min, max, Array.prototype.slice.apply(data));
    }
  }


  /**
   * http://en.wikipedia.org/wiki/Subset_sum_problem#Pseudo-polynomial_time_dynamic_programming_solution
   */
  function ssp(xs, goal) {
    var min = Math.min.apply(null, xs);
    var newRow = new BitSet(min, goal);
    var pool = [newRow];
    var maxSum = 0;

    // Forward: compute partial sums
    // NB: early exit if exact solution found
    var i = 0;
    for (; i < xs.length && maxSum < goal; ++i) {
      var prevRow = newRow;
      var newRow = prevRow.copy();
      pool.push(newRow);
      var x = xs[i];
      if (x > goal) continue;
      newRow.set(x);
      for (var j = min; j <= goal - x; ++j) {
        if (prevRow.isSet(j)) {
          newRow.set(x + j);
          maxSum = Math.max(maxSum, x + j);
        }
      }
    }

    var solution = [];
    var partialSum = maxSum;

    // Backward: extract optimal subset from row pool
    for (i = i - 1; i >= 0 && partialSum > 0; --i) {
      var x = xs[i];
      var newPartialSum = partialSum - x;
      if (newPartialSum > 0 && pool[i].isSet(newPartialSum)) {
        solution.push(x);
        partialSum = newPartialSum;
      }
      else if (newPartialSum === 0) {
        solution.push(x);
      }
    }

    return {sum: maxSum, vals: solution}
  }


  return ssp;
})();

alg2.js

subsetSumApproximate = (function(){
  'use strict';

  /** Calculate approximate subset-sum solution.
   * http://en.wikipedia.org/wiki/Subset_sum_problem#Polynomial_time_approximate_algorithm
   */
  function ssp(xs, goal, eps) {
    var pool = [{sum: 0, vals: []}];
    var delta = goal * eps / xs.length;

    for (var i = 0; i < xs.length; ++i) {
      var x = xs[i];
      var newSubsets = [];
      for (var j = 0; j < pool.length; ++j) {
        var subset = {sum: pool[j].sum + x, vals: pool[j].vals.concat([x]) };
        if (subset.sum < goal) {
          newSubsets.push(subset);
        }
        else if (subset.sum === goal) {
          return subset;
        }
      }
      pool = merge(pool, newSubsets);
      pool = trim(pool, delta);
    }
    return pool[pool.length - 1];
  }


  /** Merge two sorted arrays together.
   * NB! it can leave some duplicates but we don't care.
   */
  function merge(xs, ys) {
    var i = 0, j = 0, k = 0;
    var res = [];
    while (i < xs.length || j < ys.length) {
      var x = i < xs.length ? xs[i].sum : Number.POSITIVE_INFINITY;
      var y = j < ys.length ? ys[j].sum : Number.POSITIVE_INFINITY;
      if (x < y) {
        res[k++] = xs[i++];
      }
      else if (x === y) {
        res[k++] = xs[i++];
        ++j; // skip duplicate
      }
      else {
        res[k++] = ys[j++];
      }
    }
    return res;
  }


  /** Drop values that are Δ-close to the preceeding ones. */
  function trim(xs, delta) {
    var prev = xs[0];
    var res = [prev];
    for (var i = 1; i < xs.length; ++i) {
      var x = xs[i];
      if (x.sum > prev.sum + delta) {
        prev = x;
        res.push(x);
      }
    }
    return res;
  }


  return ssp;
})();

bench.js

onmessage = function (e) {
  'use strict';

  var d = e.data;

  // load dependencies
  for (var i = 0; i < e.data.deps.length; ++i) {
    importScripts(e.data.deps[i]);
  }


  function watch(fn) {
    var start = performance.now();
    fn();
    var end = performance.now();
    return end - start;
  }

  /** Run @f in a loop and measure its average execution time.
   * Try to choose number of iterations in a way to not exeed maxRunDuration.
   */
  function bench(f, data, goal) {
    var res;
    var draftTime = watch(function(){res = f(data, goal)});

    console.log(res.sum + ': ' + res.vals);

    var iters = draftTime < 1
        ? d.maxRunDuration
        : Math.floor(d.maxRunDuration / draftTime);
    iters = Math.max(iters, 3);

    // full run
    var fullTime = watch(function () {
        for (var i = 0; i < iters; ++i) {
          f(data, goal);
        }
      });
    return fullTime / iters;
  }

  // benchmark
  for (var szIx = 0; szIx < d.dataSizes.length; ++szIx) {
    var sz = d.dataSizes[szIx];
    postMessage({type: 'newGroup', group: sz});

    var totalTime = new Float64Array(d.funs.length);
    for (var run = 0; run < d.runsForEachSize; ++run) {
      // gen random data
      var data = new Uint32Array(sz);
      for (var i = 0; i < sz; ++i) {
        data[i] = Math.floor(Math.random() * sz);
      }

      for (var funIx = 0; funIx < d.funs.length; ++funIx) {
        var avgTime = bench(eval(d.funs[funIx]), data, sz * 25);
        totalTime[funIx] += avgTime;
        postMessage({
            type: 'results',
            group: sz,
            funIx: funIx,
            totalAvgTime: totalTime[funIx] / (run + 1)
          });
      }
    }
  }
  postMessage({type: 'done'});
}

chart.js

var BarChart = (function () {
  'use strict';

  function appendDiv(el, cls, txt) {
    var div = document.createElement('div');
    div.className = cls || '';
    div.textContent = txt || '';
    return el.appendChild(div);
  }

  function BarChart(elemId, colors, groups) {
    var chart = document.getElementById(elemId);
    var barGroups = {};

    this.addGroup = function (name, colors) {
      appendDiv(chart, 'group-label', name);
      barGroups[name] = [];

      for (var j = 0; j < colors.length; ++j) {
        barGroups[name].push({
          bar: appendDiv(chart, 'bar ' + colors[j]),
          label: appendDiv(chart, 'bar-label')
        });
      }
    };

    this.setValue = function (group, bar, val, suffix) {
      var b = barGroups[group][bar];
      b.label.textContent = val.toFixed(0) + (suffix || '');
      b.bar.style.width = Math.ceil(val/10) + 'px'; // TODO: scale
    };
  }

  return BarChart;
})();

index.html

<!DOCTYPE html>
<html>
<head>
  <meta charset="utf-8">
  <style>
    .red  { background-color: red;  opacity: 0.5 }
    .teal { background-color: teal; opacity: 0.5 }
    .chart .group-label {
      clear: both;
      font-weight: bold;
      font-size: large;
    }
    .chart .bar {
      display: inline-block;
      float: left;
      clear: left;
      margin-left: 2em;
      height: 1em;
      width: 0;
      transition:         width 1s;
      -moz-transition:    width 1s;
      -webkit-transition: width 1s;
      -o-transition:      width 1s;
    }
    .chart .bar-label {
      display: inline-block;
      float: left;
      margin-left: 0.2em;
    }
    .legend {
      display: inline-block;
      height: 1em;
      width: 1em;
      border: solid black 1px;
    }
  </style>
</head>
<body>
  <p>Сравнение скорости работы двух алгоритмов решения задачи о сумме
  подмножеств:</p>
  <ol>
    <li>
      <div class="legend red"></div>
      <a
        href="http://en.wikipedia.org/wiki/Subset_sum_problem#Pseudo-polynomial_time_dynamic_programming_solution">
        Pseudo-polynomial time dynamic programming solution
      </a>
    </li>
    <li>
      <div class="legend teal"></div>
      <a
        href="http://en.wikipedia.org/wiki/Subset_sum_problem#Polynomial_time_approximate_algorithm">
        Polynomial time approximate algorithm
      </a></li>
  </ol>
  <p>Выполняется серия тестов для разных размеров входного массива.</p>

  <div id="times" class="chart"></div>

  <script src="chart.js"></script>
  <script>
    'use strict';
    var chart1 = new BarChart('times');
    var bench = new Worker('bench.js');

    bench.onmessage = function (e) {
      var d = e.data;
      if (d.type == 'newGroup') {
        chart1.addGroup(d.group, ['red', 'teal']);
      }
      else if (d.type == 'results') {
        chart1.setValue(d.group, d.funIx, d.totalAvgTime, ' ms');
      }
      else if (d.type == 'done') {
        chart1.addGroup('Всё!', []);
      }
    };

    bench.postMessage({
      deps: ['alg1.js', 'alg2.js'],
      dataSizes: [100, 500, 1000, 5000, 10000],
      funs: [
        '(function(d, s){return subsetSumExact(d, s)})',
        '(function(d, s){return subsetSumApproximate(d, s, 0.2)})'
        ],
      maxRunDuration: 1000, // msec
      runsForEachSize: 5
    });
  </script>
</body>
</html>