2
\$\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\$
4
  • \$\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 '19 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\$ Mar 26 '19 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 '19 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 '19 at 0:20
5
\$\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\$
2
  • \$\begingroup\$ Where did you get the info that a ** 2 is slightly slower than a * a? \$\endgroup\$ Mar 27 '19 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 '19 at 12:51
1
\$\begingroup\$

Use a max-heap of at most k elements. Loop through all of the n points computing their (squared) distances to the central point. If the root of node of the heap is farther from the central point than the i'th of the n points, then discard the root and heapify with the i'th. This has time complexity n*log(k) rather than n*log(n) which is a huge difference if n >> k.

\$\endgroup\$
1
  • \$\begingroup\$ Welcome to the Code Review Community. It might be good in the future to make meaningful observations about the code as well as suggesting alternate solutions. \$\endgroup\$
    – pacmaninbw
    Nov 11 '20 at 3:40
1
\$\begingroup\$

The answers here are great, especially if you're looking to implement this algorithm in a faster way (which would be very important to do if there could potentially be a lot of points - the current implementation would be slow on large lists).

...however, I didn't see anything in the problem description about speed being a needed factor. I tend to put code quality first, avoid premature optimizations, and only speed up the code when its needed. (i.e. if there's only ever going to be at most 5 points in the list, then many speed improvements end up becoming overhead that slows the algorithm down instead of speeding it up!)

With that in mind, I actually really like the way you implemented it. It's clear and easy to understand. I'll just add a couple suggestions:

  • Like others have already pointed out, you can use Math.abs()
  • I would copy the array of points before sorting them - .sort() modifies the original array, and you generally don't want to modify function parameters.

Here's my version:

const distanceBetween = ([x1, y1], [x2, y2]) => Math.hypot(x1 - x2, y1 - y2);

const findNearestPoints = ({points, center, numberOfResults}) => {
  const distanceFromCenter = p => distanceBetween(p, center);
  return [...points]
   .sort((p1, p2) => distanceFromCenter(p1) - distanceFromCenter(p2))
   .slice(0, numberOfResults);
};

console.log(findNearestPoints({
  points: [[0, 0], [5, 4], [3, 1]],
  center: [1, 2],
  numberOfResults: 2,
}));

\$\endgroup\$

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.