CODEWITHSUNDEEP
javascriptarrayssorting
Danie Clawson
Danie Clawson

Reputation: 183

How to sort an Array of Points by their distance to a reference Point, in Javascript?

I have a working code, here:

function simpleDist(pointA, pointB) {
  var x = pointA.x - pointB.x,
      y = pointA.y - pointB.y;

  return Math.sqrt(x*x + y*y);
}

function sortByDist(pointRef, pointArray) {
  var distancePairs = [],
      output = [];

  for(var p in pointArray) {
    var pointComp = pointArray[p];

    distancePairs.push([simpleDist(pointRef,pointComp), p]);
  }

  distancePairs.sort(function(a,b) {
    return a[0]-b[0];
  });

  for(var p in distancePairs) {
    var pair = distancePairs[p];

    output.push(pointArray[pair[1]]);
  }

  return output;
}

And this works, for what I'm doing. However, I'm wondering if there is a more simplified way to do it using Array.sort(). I have looked at several explanations of Array.sort() and it seems like it would need to accept 3 functions to perform what I need without the workaround here. I feel like I'm just being dense, though. Can you see any way to make this function faster, or more simplified?

Upvotes: 1

Views: 1640

Answers (2)

Elena
Elena

Reputation: 399

UPDATE

Here is how my code can be modified to use memoize decorator. The good thing about it that memoization doesn't depend much on implementation of compared things. I am not sure though how fast is JSON.stringify() (but fast enough it seems, and hashing function can be changed after all). 

function memoized(fn) {
    var lookupTable = {};

    var keymaker = function (args) {
         console.log(JSON.stringify(args));
       return JSON.stringify(args)

    };

    return function () {
        var key = keymaker.call(this, arguments);

        return lookupTable[key] || (
        lookupTable[key] = fn.apply(this, arguments))
    }
}

function simpleDist(pointA, pointB) {
    var x = pointA.x - pointB.x,
        y = pointA.y - pointB.y;

    return Math.sqrt(x * x + y * y);
}

function distanceFrom(pointC) {
    return function (pointA, pointB) {
        var distA = simpleDist(pointA, pointC);
        var distB = simpleDist(pointB, pointC);

        if (distA < distB) return -1;
        if (distA > distB) return 1;
        return 0;
    }
}


var distanceFromC = memoized(distanceFrom({x:0, y:0}));
[{x:10, y:10}, {x:1, y:2},{x:3, y:1}, {x:3, y:2}].sort(distanceFromC);

OLD

function simpleDist(pointA, pointB) {
  var x = pointA.x - pointB.x,
      y = pointA.y - pointB.y;
  return Math.sqrt(x*x + y*y);
}

//returns comparator function for specified point
function distanceFrom(pointC) {
    return function(pointA, pointB) {
        var distA = simpleDist(pointA, pointC);
        var distB = simpleDist(pointB, pointC);

        if (distA < distB)
            return -1;
        if (distA > distB)
            return 1;
        return 0;
    }
}

//now we can create separator functions for each ponts we like 
var distanceFromC = distanceFrom({x:0, y:0});
var distanceFromD = distanceFrom({x:10, y:10});

//just keep  in mind that built-in sort modifies initial list
console.log([{x:10, y:10}, {x:1, y:2}].sort(distanceFromC)); //{1,2}, {10,10}
console.log([{x:10, y:10}, {x:1, y:2}].sort(distanceFromD)); //{10,10}, {1,2}

Here I used the fact that closures and the fact that they can access outer function parameters even after outer function returns. You can read more about it, for example, in David Herman's Effective Javascript chapter 2.11 or here

Upvotes: 3

J. Holmes
J. Holmes

Reputation: 18546

I think that you are pretty much on the right track.

If you are trying to optimize for lines of code, then you can use Array.prototype.map to reduce some the boiler-plate array code.

Using a similar sorting implementation 

function simpleDist(pointA, pointB) {
  var x = pointA.x - pointB.x,
      y = pointA.y - pointB.y;

  return Math.sqrt(x*x + y*y);
}

var sortByDist = (function() {
  var comparator = function(a,b) { return a.value - b.value; };

  return function (pointRef, pointArray) {
    var reorder = function(e) { return pointArray[e.index]; };
    var distanceFromArray = function(b,i) {
      return { index: i, value: simpleDist(pointRef, b) };
    };
    return pointArray.map(distanceFromArray).sort(comparator).map(reorder);
  };
}());

The only "direct" way I can think to simplify the implementation would be to use memoization to optimize calls to simpleDist.

function simpleDist(pointA, pointB) {
  var x = pointA.x - pointB.x,
      y = pointA.y - pointB.y;

  return Math.sqrt(x*x + y*y);
}

// fn(point) memoizer    
var memoizer = (function(fn) {
  var cache = {};
  return function(pointB) {
    var key = pointB.x + "|" + pointB.y; // simple key hashing 
    return cache[key] || (cache[key] = fn(pointB));
  };
}());

function sortByDist (pointRef, pointArray) {
  // partially apply pointRef to simpleDist and memoize
  var distanceFrom = memoizer(function(pointB) { return simpleDist(pointRef, pointB); });

  // sort
  return pointArray.sort(function(a,b) {
    return distanceFrom(a) - distanceFrom(b);
  });
}

Given that simpleDist is a pure function -- the same inputs always produce the same outputs -- the memoizer here prevents you from incurring the cost of repeated distance calculations. With a little more setup overhead, then the sort becomes a simple comparator.

Upvotes: 3

Related Questions