# [Scilab-users] need a little help

11 messages
Open this post in threaded view
|

## [Scilab-users] need a little help

 Hi experts,my problem is (I guess) a very common thing, but I somehow get stucked.I aim to find the nearest position of ANY value in array_1 to ANY position in array_2.e.g.:A = array of doubles with 1000 elements.B = array of doubles with 10'000 elements.for each element of A I want to know it's nearest value in B.Also I want to know the index of the nearest value in B.I could do it in a bunch of for-loops, but this is way to slow, since this loops 1000 values against 10'000 values of B.something like this:nearesVal   = zeros(1000);distIndex    = zeros(1000);for i=1:1000  d = 1000000; // just a rediculous big number that is much greater than max(A) & max(B)   for j = 1:10000     act_dist = abs( A(i) - B(j) );     // actual minimal distance        if act_dist <= d        d = act_dist;        nearestVal(i) = B(j);         distIndex(i)  = j;      end   endendI do not have Scilab at hand, while I am writing this, but it looks like it should work :-)ThanksPhil _______________________________________________ users mailing list [hidden email] http://lists.scilab.org/mailman/listinfo/users
Open this post in threaded view
|

## Re: need a little help

 A simpler way -- outarr=zeros(1000) for i=1:1000 [m,k]=min(abs(B-A(i)); outarr(i)=k; end; This will produce a list in outarr such that outarr(n) is the index of the element in B closest to the n'th element in A . If you want to go faster, consider setting up  a binary tree containing B.  Then use the tree to search for nearest neighbor to A(i) and to -A(i). Then decide which neighbor is closer.  (I think this works). Searching the tree goes as log of length of B at the expense of a linear time in setting it up. For some length of B this will win. S   "P M" ---02/15/2019 03:58:32 PM---Hi experts, my problem is (I guess) a very common thing, but I somehow get stucked. From: "P M" <[hidden email]> To: "International users mailing list for Scilab." <[hidden email]> Date: 02/15/2019 03:58 PM Subject: [Scilab-users] need a little help Sent by: "users" <[hidden email]> Hi experts, my problem is (I guess) a very common thing, but I somehow get stucked. I aim to find the nearest position of ANY value in array_1 to ANY position in array_2. e.g.: A = array of doubles with 1000 elements. B = array of doubles with 10'000 elements. for each element of A I want to know it's nearest value in B. Also I want to know the index of the nearest value in B. I could do it in a bunch of for-loops, but this is way to slow, since this loops 1000 values against 10'000 values of B. something like this: nearesVal   = zeros(1000); distIndex    = zeros(1000); for i=1:1000   d = 1000000; // just a rediculous big number that is much greater than max(A) & max(B)   for j = 1:10000      act_dist = abs( A(i) - B(j) );     // actual minimal distance        if act_dist <= d         d = act_dist;         nearestVal(i) = B(j);         distIndex(i)  = j;       end    end end I do not have Scilab at hand, while I am writing this, but it looks like it should work :-) Thanks Phil _______________________________________________ users mailing list [hidden email] http://lists.scilab.org/mailman/listinfo/users _______________________________________________ users mailing list [hidden email] http://lists.scilab.org/mailman/listinfo/users
Open this post in threaded view
|

## Re: need a little help

 In reply to this post by der_Phil Hello Phil, This should work: --> [A,B] = ndgrid(rand(1,1000), rand(1,10000));  // test's data --> size(A)  ans  =    1000.   10000. --> [v, i] = min(abs(A-B)); The minimal distances are in v, the index of the closest in B are in i. Regards Samuel Le 15/02/2019 à 21:46, P M a écrit : Hi experts, my problem is (I guess) a very common thing, but I somehow get stucked. I aim to find the nearest position of ANY value in array_1 to ANY position in array_2. e.g.: A = array of doubles with 1000 elements. B = array of doubles with 10'000 elements. for each element of A I want to know it's nearest value in B. Also I want to know the index of the nearest value in B. I could do it in a bunch of for-loops, but this is way to slow, since this loops 1000 values against 10'000 values of B. something like this: nearesVal   = zeros(1000); distIndex    = zeros(1000); for i=1:1000   d = 1000000; // just a rediculous big number that is much greater than max(A) & max(B)   for j = 1:10000      act_dist = abs( A(i) - B(j) );     // actual minimal distance        if act_dist <= d         d = act_dist;         nearestVal(i) = B(j);         distIndex(i)  = j;       end    end end I do not have Scilab at hand, while I am writing this, but it looks like it should work :-) Thanks Phil ```_______________________________________________ users mailing list [hidden email] http://lists.scilab.org/mailman/listinfo/users ``` _______________________________________________ users mailing list [hidden email] http://lists.scilab.org/mailman/listinfo/users
Open this post in threaded view
|

## Re: need a little help

 In reply to this post by der_Phil Sorry, instead of my previous message, please read --> [A,B] = ndgrid(rand(1,1000), rand(1,10000));  // test's data --> size(A)  ans  =    1000.   10000. --> [v, i] = min(abs(A-B), "c"); Samuel _______________________________________________ users mailing list [hidden email] http://lists.scilab.org/mailman/listinfo/users
Open this post in threaded view
|

## Re: need a little help

 ... and even clearer, with respect to your own notations: --> A = rand(1,1000);  // test's data --> B = rand(1,10000); --> [a, b] = ndgrid(A, B); --> size(a)  // same for b  ans  =    1000.   10000. --> [v, i] = min(abs(a-b), "c"); _______________________________________________ users mailing list [hidden email] http://lists.scilab.org/mailman/listinfo/users
Open this post in threaded view
|

## Re: need a little help

 Ok, thanks for your help..Actually the sizes I gave where just for demonstation.If I use the real array sizes, I get a message: can not allocate  7469.60MB memory...which maybe is true.available RAM after starting Scilab is 3701 MBactual array sizes:A has 1076 elementsB has 1'350'000 elements, with a lot of Nan's in itif I use thrownan(B) I can reduce the array size of B to 867751 elements but still get the Message above.(without thrownan() the memory scilab wants to allocate is even bigger)Am Fr., 15. Feb. 2019 um 23:25 Uhr schrieb Samuel Gougeon <[hidden email]>: ... and even clearer, with respect to your own notations: --> A = rand(1,1000);  // test's data --> B = rand(1,10000); --> [a, b] = ndgrid(A, B); --> size(a)  // same for b  ans  =    1000.   10000. --> [v, i] = min(abs(a-b), "c"); _______________________________________________ users mailing list [hidden email] http://lists.scilab.org/mailman/listinfo/users _______________________________________________ users mailing list [hidden email] http://lists.scilab.org/mailman/listinfo/users
Open this post in threaded view
|

## Re: need a little help

 problem solved.....I had to think differently than before.Actually my goal was to compare point coordinates to map coordinates and find the points on the map which are closest to the given point coordinates.The map is of width:    900    // in reality the map is based on an image with 900x1500 pixelsThe map is of height: 1500The points are building a line on the map...e.g: the line consists of 1076 pointsSo from the map I have build:x = map(1,:);   // contains all x coordinates of the mapy = map(2,:);   // contains all y coordinates of the mappoints = [ lineX, lineY];      // points contain the X-Y-coordinates of the linefor i = 1:n     actPoint = points(i,:);     [nearestX xInd]   = min(abs(actPoint(1)-x));     [nearestY yInd]  = min(abs(actPoint(2)-y));     nearestPoint(i,:) = [x(xInd) y(yInd)];endThis is what works for now, though it is still slow.For searching 100 points of the line it needs about 10 seconds.For searching 200 points of the line it needs about 19 seconds.For searching 500 points of the line it needs about 45 seconds.For searching 1000 points of the line it needs about 98 seconds.Am Mo., 18. Feb. 2019 um 16:39 Uhr schrieb P M <[hidden email]>:Ok, thanks for your help..Actually the sizes I gave where just for demonstation.If I use the real array sizes, I get a message: can not allocate  7469.60MB memory...which maybe is true.available RAM after starting Scilab is 3701 MBactual array sizes:A has 1076 elementsB has 1'350'000 elements, with a lot of Nan's in itif I use thrownan(B) I can reduce the array size of B to 867751 elements but still get the Message above.(without thrownan() the memory scilab wants to allocate is even bigger)Am Fr., 15. Feb. 2019 um 23:25 Uhr schrieb Samuel Gougeon <[hidden email]>: ... and even clearer, with respect to your own notations: --> A = rand(1,1000);  // test's data --> B = rand(1,10000); --> [a, b] = ndgrid(A, B); --> size(a)  // same for b  ans  =    1000.   10000. --> [v, i] = min(abs(a-b), "c"); _______________________________________________ users mailing list [hidden email] http://lists.scilab.org/mailman/listinfo/users _______________________________________________ users mailing list [hidden email] http://lists.scilab.org/mailman/listinfo/users
Open this post in threaded view
|

## Re: need a little help

 ..update: removing all NaN's from the map it takes about 27seconds to find all nearest points...I think, I can live with that...unless somebody else has another brilliant idea.best regards,PhilippAm Mo., 18. Feb. 2019 um 18:08 Uhr schrieb P M <[hidden email]>:problem solved.....I had to think differently than before.Actually my goal was to compare point coordinates to map coordinates and find the points on the map which are closest to the given point coordinates.The map is of width:    900    // in reality the map is based on an image with 900x1500 pixelsThe map is of height: 1500The points are building a line on the map...e.g: the line consists of 1076 pointsSo from the map I have build:x = map(1,:);   // contains all x coordinates of the mapy = map(2,:);   // contains all y coordinates of the mappoints = [ lineX, lineY];      // points contain the X-Y-coordinates of the linefor i = 1:n     actPoint = points(i,:);     [nearestX xInd]   = min(abs(actPoint(1)-x));     [nearestY yInd]  = min(abs(actPoint(2)-y));     nearestPoint(i,:) = [x(xInd) y(yInd)];endThis is what works for now, though it is still slow.For searching 100 points of the line it needs about 10 seconds.For searching 200 points of the line it needs about 19 seconds.For searching 500 points of the line it needs about 45 seconds.For searching 1000 points of the line it needs about 98 seconds.Am Mo., 18. Feb. 2019 um 16:39 Uhr schrieb P M <[hidden email]>:Ok, thanks for your help..Actually the sizes I gave where just for demonstation.If I use the real array sizes, I get a message: can not allocate  7469.60MB memory...which maybe is true.available RAM after starting Scilab is 3701 MBactual array sizes:A has 1076 elementsB has 1'350'000 elements, with a lot of Nan's in itif I use thrownan(B) I can reduce the array size of B to 867751 elements but still get the Message above.(without thrownan() the memory scilab wants to allocate is even bigger)Am Fr., 15. Feb. 2019 um 23:25 Uhr schrieb Samuel Gougeon <[hidden email]>: ... and even clearer, with respect to your own notations: --> A = rand(1,1000);  // test's data --> B = rand(1,10000); --> [a, b] = ndgrid(A, B); --> size(a)  // same for b  ans  =    1000.   10000. --> [v, i] = min(abs(a-b), "c"); _______________________________________________ users mailing list [hidden email] http://lists.scilab.org/mailman/listinfo/users _______________________________________________ users mailing list [hidden email] http://lists.scilab.org/mailman/listinfo/users
Open this post in threaded view
|

## Re: need a little help

In reply to this post by der_Phil
Hi Philipp

>problem solved.....I had to think differently than before.

Heh!

It helps to know what you actually want to do (and also the size of the problem).

Cheers,
Claus

On 18.02.2019 18:08, P M wrote:
problem solved.....I had to think differently than before.

Actually my goal was to compare point coordinates to map coordinates and find the points on the map which are closest to the given point coordinates.

The map is of width:    900    // in reality the map is based on an image with 900x1500 pixels
The map is of height: 1500

The points are building a line on the map...e.g: the line consists of 1076 points
So from the map I have build:

x = map(1,:);   // contains all x coordinates of the map
y = map(2,:);   // contains all y coordinates of the map

points = [ lineX, lineY];      // points contain the X-Y-coordinates of the line

for i = 1:n
actPoint = points(i,:);
[nearestX xInd]   = min(abs(actPoint(1)-x));
[nearestY yInd]  = min(abs(actPoint(2)-y));
nearestPoint(i,:) = [x(xInd) y(yInd)];
end

This is what works for now, though it is still slow.

For searching 100 points of the line it needs about 10 seconds.
For searching 200 points of the line it needs about 19 seconds.
For searching 500 points of the line it needs about 45 seconds.
For searching 1000 points of the line it needs about 98 seconds.

Am Mo., 18. Feb. 2019 um 16:39 Uhr schrieb P M <[hidden email]>:

Actually the sizes I gave where just for demonstation.

If I use the real array sizes, I get a message: can not allocate  7469.60MB memory...which maybe is true.
available RAM after starting Scilab is 3701 MB

actual array sizes:

A has 1076 elements
B has 1'350'000 elements, with a lot of Nan's in it

if I use thrownan(B) I can reduce the array size of B to 867751 elements but still get the Message above.

(without thrownan() the memory scilab wants to allocate is even bigger)

Am Fr., 15. Feb. 2019 um 23:25 Uhr schrieb Samuel Gougeon <[hidden email]>:
... and even clearer, with respect to your own notations:

--> A = rand(1,1000);  // test's data
--> B = rand(1,10000);

--> [a, b] = ndgrid(A, B);

--> size(a)  // same for b
ans  =
1000.   10000.
--> [v, i] = min(abs(a-b),
"c");

_______________________________________________
users mailing list
[hidden email]
http://lists.scilab.org/mailman/listinfo/users

```_______________________________________________
users mailing list
[hidden email]
http://lists.scilab.org/mailman/listinfo/users
```

 Virus-free. www.avast.com

_______________________________________________
users mailing list
[hidden email]
http://lists.scilab.org/mailman/listinfo/users
Open this post in threaded view
|

## Re: need a little help

@ Claus:

...well actually I wanted to treat every coordinate separatly....so A would be my X coordinate of the map and B would be the x coordinate of the line.
Afterwarsd I would do the same with the Y-coordinate..

So I think my question expressed what I wanted to do in the beginning.

What I did not expect was, that the size of the arrays would matter  (did not expect this memory issue).

Anyways....of course you are right.
Cheers,
Philipp

Am Mo., 18. Feb. 2019 um 18:32 Uhr schrieb Claus Futtrup <[hidden email]>:
Hi Philipp

>problem solved.....I had to think differently than before.

Heh!

It helps to know what you actually want to do (and also the size of the problem).

Cheers,
Claus

On 18.02.2019 18:08, P M wrote:
problem solved.....I had to think differently than before.

Actually my goal was to compare point coordinates to map coordinates and find the points on the map which are closest to the given point coordinates.

The map is of width:    900    // in reality the map is based on an image with 900x1500 pixels
The map is of height: 1500

The points are building a line on the map...e.g: the line consists of 1076 points
So from the map I have build:

x = map(1,:);   // contains all x coordinates of the map
y = map(2,:);   // contains all y coordinates of the map

points = [ lineX, lineY];      // points contain the X-Y-coordinates of the line

for i = 1:n
actPoint = points(i,:);
[nearestX xInd]   = min(abs(actPoint(1)-x));
[nearestY yInd]  = min(abs(actPoint(2)-y));
nearestPoint(i,:) = [x(xInd) y(yInd)];
end

This is what works for now, though it is still slow.

For searching 100 points of the line it needs about 10 seconds.
For searching 200 points of the line it needs about 19 seconds.
For searching 500 points of the line it needs about 45 seconds.
For searching 1000 points of the line it needs about 98 seconds.

Am Mo., 18. Feb. 2019 um 16:39 Uhr schrieb P M <[hidden email]>:

Actually the sizes I gave where just for demonstation.

If I use the real array sizes, I get a message: can not allocate  7469.60MB memory...which maybe is true.
available RAM after starting Scilab is 3701 MB

actual array sizes:

A has 1076 elements
B has 1'350'000 elements, with a lot of Nan's in it

if I use thrownan(B) I can reduce the array size of B to 867751 elements but still get the Message above.

(without thrownan() the memory scilab wants to allocate is even bigger)

Am Fr., 15. Feb. 2019 um 23:25 Uhr schrieb Samuel Gougeon <[hidden email]>:
... and even clearer, with respect to your own notations:

--> A = rand(1,1000);  // test's data
--> B = rand(1,10000);

--> [a, b] = ndgrid(A, B);

--> size(a)  // same for b
ans  =
1000.   10000.
--> [v, i] = min(abs(a-b),
"c");

_______________________________________________
users mailing list
[hidden email]
http://lists.scilab.org/mailman/listinfo/users

```_______________________________________________
users mailing list
[hidden email]
http://lists.scilab.org/mailman/listinfo/users
```

 Virus-free. www.avast.com
_______________________________________________
users mailing list
[hidden email]
http://lists.scilab.org/mailman/listinfo/users

_______________________________________________
users mailing list
[hidden email]
http://lists.scilab.org/mailman/listinfo/users