how to make my searching matrix faster faster ??

[ppcandy]

dear friends,
I have this program to search in big matrix for a value that is closest to a certain number My question is if there is a way to make this process faster besides two loops: ?? it is just too slow

problem in detail: there is a location. Its x,y coordinates is (xs,ys). There also are many locations defined by X-matrix and Y-matrix, both are mxn big size.
now find which one in these locations that is closest to (xs,ys)

what I did is calculate distance between (xs,ys) and each location defined by X,Y matrix and compare the smallest value. see bellow. Anyone has better idea ?

zmin=100;
for (i=1;i<m;i++)
{
for (j=2;j<n;j++)
{
if ((sqrt(pow((xs-X[i][j]),2)+pow((ys-Y[i][j]),2)))<zmin)
{
recordI = i;
recordJ = j;
zmin=sqrt(pow((xs-X[i][j]),2)+pow((ys-Y[i][j]),2));

}

}

}

[hamsterman]

You can't avoid iterating through all values.
In situations like this, I always thought that sqrt was the culprit. After a quick benchmark, apparently pow is much slower. Anyway, you don't have any reason to use either. Do (xs-X[i][j])*(xs-X[i][j])+(ys-Y[i][j])*(ys-Y[i][j])<zmin*zmin or zmin_squared, depending on how yuo want to have the zmin = ... line (with or without sqrt).
By the way, why do you not start from 0, 0?

[ppcandy]

thanks a lot for 'pow' infor. I didn't know that.
starting from 2 is just the physics reason.

[ne555]

You can't avoid iterating through all values.

Yes, you can.
By instance, using a quadtree.

[hamsterman]

I don't see it. Do you mean a heap? It's kind of complicated with two variables. And I bet it would make the rest of the code awkward.

[ne555]

No, I mean a tree.
You divide the space in 4 regions.
if there are enough points inside a region, you will subdivide it.

Now you take your 'query' point, and determine its region.
Its nearest neighbour is either there, or in a neighbour region.

[Gaminic]

Alternatively, an easier alternative to Quadtree-ish structures is Pigeon Holing: plot a grid over your map and assign points to the grid based on their coordinates. For every point, the nearest neighbor is either in its own square, or in one of the 8 surrouding ones. Depending on the density, you can toy around with the grid-square size.

Basically, it's a "single-layer" Quadtree; a Quadtree would recursively subdivide high-density areas. This leads to much better performance on unbalanced maps, but does make it much more difficult!

[mik2718]

If the same matrix is being searched multiple times with different queries then a more complicated data structure would be appropriate.

If just once then it wouldn't be.

The original post does not indicate which.