Info

Given an array of price points what's the fastest way to find the best point at which to buy and sell?

Preparation code

 
<script>
  Benchmark.prototype.setup = function() {
    var entropy = 1000;
    var points = Array(entropy);
    for (i = 0; i < points.length; i++) {
      points[i] = Math.floor(Math.random() * entropy);
      if (i > 0) {
        if (Math.round(Math.random() % 2)) { // sometimes add
          points[i] = points[i - 1] + points[i];
        } else { // sometimes subtract
          points[i] = points[i - 1] - points[i];
        }
        // don't go into the red
        points[i] = Math.abs(points[i]);
      } else {
        // start from a random point
        points[i] = Math.round(Math.random() * entropy * entropy);
      }
    }
  };
</script>

Test runner

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

Java applet disabled.

sorted = points.slice(0).sort(function(a, b) {
  return a - b;
});
best = false;
i = 0;
while (!best && i < sorted.length) {
  low = sorted[0 + i];
  high = sorted[sorted.length - 1];
  lowi = points.lastIndexOf(low);
  highi = points.lastIndexOf(high);
  if (lowi < highi) {
    best = {
      buy: lowi,
      sell: highi,
      profit: high - low
    };
  }
  i++;
}

best = {
  profit: 0
};
for (i = 0; i < points.length; i++) {
  remaining = points.slice(i);
  var pointBest = {
    profit: 0
  };
  for (j = i; j < points.length; ++j) {
    profit = points[j] - points[i];
    if (profit > pointBest.profit) {
      pointBest = {
        profit: profit,
        buy: i,
        sell: j
      };
    }
  }
  if (best.profit <= pointBest.profit) {
    best = pointBest;
  }
}

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

Compare results of other browsers

0 comments