Tell me more ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 3 down vote favorite
1

I've written this following rather naïve branch-and-bound based IP solver. My question is whether there are any obvious JavaScript optimisations that could speed it up? I am not looking for asymptotically better algorithms, just simple speed optimisations effective on problem sizes with 5-6 variables and minSize values up to about 500.

/** Represents a simple 1-dimensional 
 * IP (Integer Programming) problem.
 * @constructor
 * @param {Array<size: Number, cost: Number>} priceList
 *   List of costs for given sizes.
 *   Note that this list will be sorted by this constructor.
 */
function Prices (priceList) {
  this.prices = priceList;
  this.prices.sort (PriceCompare);
  this.minimise = PricesMinimise;
  this.pricesBB = PricesBB;
}

/** Solves the simple 1-dimensional IP problem:
 * Minimise Sum_i cost_i * x_i
 *    where Sum_i size_i * x_i >= minSize
 *      and cost_i, size_i are positive reals,
 *      and x_i is a nonnegative integer. (i = 0..prices.length - 1)
 *
 * cost_i = this.prices[i].cost and size_i = this.prices[i].size.
 *
 * @param {Number} minSize  The minimum size that must be supplied.
 * @return {xs: Array, cost: Number}  [x_0, x_1, ...] and total cost.
 */
function PricesMinimise (minSize) {
  this.minSize = minSize;
  this.incumbent = Number.POSITIVE_INFINITY;
  this.maxCost = Number.POSITIVE_INFINITY;
  var xsCost = this.pricesBB (0, 0, 0, 0);
  xsCost.xs.reverse ();
  return xsCost;
}

/** Solves a sub problem using only price list elements with
 * index >= i.  It uses instance fields
 * minSize: the minimum required size sum,
 * incumbent: lowest full solution cost seen so far,
 * maxCost: upper bound on full solution cost.
 * @param {Number} i        Minimum price list index.
 * @param {Number} sizeSum  Size sum already selected.
 * @param {Number} costSum  Cost sum already spent.
 * @param {Number} minCost  Lower bound on full solution cost in this
 *                          subtree.
 * @return {xs: Array, cost: Number}  A minimum candidate
 *   solution, or null if none better than the incumbent were
 *   found.
 */
function PricesBB (i, sizeSum, costSum, minCost) {
  var price = this.prices [i];
  var size = price.size;
  var cost = price.cost;
  var xReal = (this.minSize - sizeSum) / size;
  var x = Math.ceil (xReal);
  var localCostSum;
  if (size == Number.POSITIVE_INFINITY) {
    x = 1;
    size = 0; // Avoid NaN in recursive call
    localCostSum = cost;
  } else {
    localCostSum = costSum + cost * x;
    var localMinCost = costSum + cost * xReal;
    minCost = Math.max (minCost, localMinCost);
    if (localMinCost >= this.incumbent) return null;
  }
  this.maxCost = Math.min (this.maxCost, localCostSum);
  var localMin = {'xs': [x], 'cost': localCostSum};
  if (localCostSum < this.incumbent) this.incumbent = localCostSum;
  if (localCostSum == minCost) return localMin;
  if (i < this.prices.length - 1)
    for (x--; x >= 0; x--) {
      var xsCost =
        this.pricesBB (i + 1, sizeSum + size * x, costSum + cost * x, minCost);
      if (xsCost == null) continue;
      xsCost.xs.push (x);
      localMin = xsCost;
      if (localMin.cost == minCost) return localMin;
    }
  if (localMin.cost == this.incumbent)
    return localMin;
  else
    return null;
}
share|improve this question
1  
I'll try to take a more serious look at this if it's still not answered when I have more time, but for starters, anywhere you can use "===" instead of "==" would be good. "==" performs type coercion in JS (which allows "5" == 5 to return true), whereas "===" does not. – TheXenocide Feb 10 '11 at 22:56
To be honest, that code looks horrible, either clean it up or provide some tests, otherwise chances are very high that any attempt by us to optimize it, will break it. – Ivo Wetzel Feb 13 '11 at 11:22
Please provide the definition of PriceCompare and context for the optimization: which methods do you call, what does the data look like... – Eric Bréchemier Feb 13 '11 at 12:55
Ivo, I'd be happy to clean up the code if you explain me what you had in mind. Especially, of course, if it would speed it up :-) – Arne Feb 13 '11 at 13:44
TheXenocide, will type coercion also incur a cost in places where the types are already identical? Eric, sorry for leaving out PriceCompare---it compares two prices by comparing their cost per size. Anyway, I wasn't really thinking of algorithmic optimisations, rather of JavaScript-related speedups. To use this code, you first construct a Price object using new Price(...), then you call its minimise method. – Arne Feb 13 '11 at 13:52
show 7 more comments

migrated from stackoverflow.com Feb 10 '11 at 2:41

1 Answer

up vote 2 down vote accepted

Nowadays we have great tools at our disposal, one of them is The Closure Compiler from Google, which is a tool for making JavaScript download and run faster. It parses your JavaScript, analyzes it, removes dead code and rewrites and minimizes what's left. It also checks syntax, variable references, and types, and warns about common JavaScript pitfalls.

So, the web version of Closure Compiler gave me the following recommendations for your snippet:

  1. Example, this.incumbent = Number.POSITIVE_INFINITY; this.maxCost = Number.POSITIVE_INFINITY; becomes this.maxCost = this.incumbent = Number.POSITIVE_INFINITY;
  2. Other obvious speed enhancements that can be automated with minification:
    • Use parameters as a variable instead of another var: var minSize = this.pricesBB(0, 0, 0, 0);
    • Reuse var's when they are longer in user in a function instead of declaring new ones
    • Shorten variable names (parsing speed issue)
    • var price = this.prices [i]; var size = price.size; becomes var price = this.prices[i], g = price.size;

The full result of the Closure Compiler for your piece Javascript: 

function Prices(c) {
  this.prices = c;
  this.prices.sort(PriceCompare);
  this.minimise = PricesMinimise;
  this.pricesBB = PricesBB
}
function PricesMinimise(c) {
  this.minSize = c;
  this.maxCost = this.incumbent = Number.POSITIVE_INFINITY;
  c = this.pricesBB(0, 0, 0, 0);
  c.xs.reverse();
  return c
}
function PricesBB(c, i, h, f) {
  var e = this.prices[c], g = e.size;
  e = e.cost;
  var a = (this.minSize - i) / g, d = Math.ceil(a), b;
  if(g == Number.POSITIVE_INFINITY) {
    d = 1;
    g = 0;
    b = e
  }else {
    b = h + e * d;
    a = h + e * a;
    f = Math.max(f, a);
    if(a >= this.incumbent) {
      return null
    }
  }
  this.maxCost = Math.min(this.maxCost, b);
  a = {xs:[d], cost:b};
  if(b < this.incumbent) {
    this.incumbent = b
  }
  if(b == f) {
    return a
  }
  if(c < this.prices.length - 1) {
    for(d--;d >= 0;d--) {
      b = this.pricesBB(c + 1, i + g * d, h + e * d, f);
      if(b != null) {
        b.xs.push(d);
        a = b;
        if(a.cost == f) {
          return a
        }
      }
    }
  }
  return a.cost == this.incumbent ? a : null
}
;
share|improve this answer
Thanks, this is really helpful! – Arne Mar 22 '11 at 20:16

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.