1
\$\begingroup\$

The task:

Given a list of points, a central point, and an integer k, find the nearest k points from the central point.

For example, given the list of points [(0, 0), (5, 4), (3, 1)], the central point (1, 2), and k = 2, return [(0, 0), (3, 1)].

My solution:

const lst = [[0, 0], [5, 4], [3, 1]];
const center = [1, 2];
const k = 2;

const findNearestPoints = ({lst, center, k}) => {
  // I assume the data are valid; no error checks
  const calcHypo = x => Math.sqrt((x[0] - center[0])**2
                                + (x[1] - center[1])**2);
  const sortPoints = (a,b) => calcHypo(a) - calcHypo(b);
  return lst
   .sort(sortPoints)
   .slice(0,k);
};

console.log(findNearestPoints({lst, center, k}));
\$\endgroup\$
  • \$\begingroup\$ First thing that popped into my mind is that there actually exists a hypotenuse function in the Math global which you could use (Math.hypot). \$\endgroup\$ – morbusg Mar 26 at 15:21
  • \$\begingroup\$ Computing a square root (or two of them, actually) on every comparison can get expensive. With a thousand points, you're doing 20x more math than necessary. Caching hypotenuse lengths can be a good time-space trade, if speed is more important than memory conservation. \$\endgroup\$ – Oh My Goodness Mar 26 at 16:02
  • \$\begingroup\$ @morbusg Math.hypot is multi dimensional \$O(n)\$ where n is number of dimensions and as such has a hefty overhead associated with vetting and iterating the argument array. For 2D hypotenuse (x*x+y*y)**0.5 is much quicker \$\endgroup\$ – Blindman67 Mar 27 at 0:17
  • 1
    \$\begingroup\$ @OhMyGoodness the hypotenuse is not needed, the square of the hypotenuse can be used to compare differences in distance. \$\endgroup\$ – Blindman67 Mar 27 at 0:20
3
\$\begingroup\$

Don't sqrt the distance.

It is a common mistake when filtering distances to use the complete distance calculation.

Given 2 values a and b, if a < b then it is also true that sqrt(a) < sqrt(b). Hence you don't need the expensive sqrt calculation to know the if a point is closer than another.

To find the closest the following does not use the sqrt of the distance.

function closestPoint(points, point, dist){
    var x, y, found, min = dist * dist; // sqr distance
    for(const p of points) {
        x = p[0] - point[0];
        y = p[1] - point[1];
        x *= x;
        y *= y;
        if(x + y < min){
            min = x + y;
            if (min === 0) { return p } // early exit
            found = p;
        }
    }
    return found;

}

Not in the sort!!!

You are doing the distance calculation in the sort DON'T!!!, that means you repeat the same calculations over and over.

To improve you throughput the following will reduce the over all time. The improvement is linear and does not change the complexity.

Note that in JS a ** 2 is slightly slower than a * a

A more efficient version of your solution

function findNearestPoints({list, center, k}) {
    const res = [];
    const cx = center[0], cy = center[1]; // alias and reduce indexing overhead
    const distSqr = (x, y) => (x -= cx) * x + (y -= cy) * y;
    const sort = (a, b) => a[1] - b[1];

    for (const p of list) { res.push([p, distSqr(p[0], p[1])]) }
    res.sort(sort).length = k;
    return res.map(p => p[0]);
}

The ** operator for roots

Note that JS has the ** operator. That you can use it to get roots by making the right side the inverse, 1 over the power. Thus the sqrt is **(1/2) the cube root is **(1/3)

eg

if 2 ** 2 === 4 then 4 ** (1/2) === 2
if 2 ** 3 === 8 then 8 ** (1/3) === 2  Don't approximate 8 ** 0.33 !== 2
if 2 ** 4 === 16 then 16 ** (1/4) === 2

Better sort

The sort is the bottle neck in this problem.

You can use a binary tree sort as it is the least complex for real numbers (every coder should learn how to implement a binary tree sort)

Do you need the sort?

However I think (think means might be, I am going by instinct) that there is a faster solution that does not involve a sort and that is at most \$O(n)\$

Remember that the order of the points is not important, that you need only separate the points in two. It may take a few passes to do, but as long as the number of passes is not related to the number of points or 'k' you will have a \$O(n)\$ solution.

I am not going to give you the solution this time (if there is one) as there is no problem solving experienced gained coping code.

\$\endgroup\$
  • \$\begingroup\$ Where did you get the info that a ** 2 is slightly slower than a * a? \$\endgroup\$ – thadeuszlay Mar 27 at 11:15
  • \$\begingroup\$ @thadeuszlay I bench-mark it. I just retested on Chrome 73 and its gotten worse. Comparative results n * n fastest. n is random number. (The following % are percent as fast as best eg 50% is half the speed). Math.pow(n, 2) very close 99% for small ints and same performance for large doubles. n ** 2 is 36% for random large doubles 0 to \$2^{51}\$ and random ints 0 to \$2^{31}\$, and 24% for random small ints 0 to \$2^8\$. On FF all 3 are the same however all are only 20% as fast as Chromes best. \$\endgroup\$ – Blindman67 Mar 27 at 12:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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