Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
Determine whether the number is in a given range

Subject: Determine whether the number is in a given range

From: m4 Chrennikov

Date: 21 Jan, 2011 14:35:20

Message: 1 of 6

Hi all.
I want to check if numbers are in a given range. Range represented with 2 other matricies, one for first value of the range other for second. For ex:
a=[1 2 3];
r1=[0 3 2];
r2=[2 4 3];
now I'm doing something like that
nums = sparse( a>r1 & a<r2 )
nums =
    1 0 0
Is there more efficient way to do that?
Actually vector a is Nx1 and vectors r1 & r2 are both 1xM. And result matrix nums should be NxM. Now I clone both a and r1/r2 vectors, so they have the same size:
a=[1;2;3];
a=a(:,ones(1,M));
r1=[0 3 2];
r1=r1(ones(1,N),:);
r2=[2 4 3];
r2=r2(ones(1,N),:);
nums = sparse( a>r1 & a<r2 )
nums =
    1 0 0
    0 0 0
    0 0 0
The questions are:
How can I obtain nums NxM matrix without allocation cloned matricies a, r1, r2? I'm asking that because this("cloned") matricies are using lot of memory(more than 90% comparig to all other variables), so with fine a mesh I reach "out of memory" message.
Is there any way to speedup relational operations, allocating result sparse matix?

For clarity, I will describe my problem: I have some distribution of "zones"
http://homepage.corbina.net/~skarelin/zone_distr.png
start and end angle of each zone represented in r1 and r2 vectors. And a vector contains angles(computed on some x y z mesh). I need to know for each a element which zones belong to this angle.

Subject: Determine whether the number is in a given range

From: Paulo Silva

Date: 21 Jan, 2011 15:01:05

Message: 2 of 6

"m4 Chrennikov" <abrek77@gmail.com> wrote in message <ihc5j8$bie$1@fred.mathworks.com>...
> Hi all.
> I want to check if numbers are in a given range. Range represented with 2 other matricies, one for first value of the range other for second. For ex:
> a=[1 2 3];
> r1=[0 3 2];
> r2=[2 4 3];
> now I'm doing something like that
> nums = sparse( a>r1 & a<r2 )
> nums =
> 1 0 0
> Is there more efficient way to do that?
> Actually vector a is Nx1 and vectors r1 & r2 are both 1xM. And result matrix nums should be NxM. Now I clone both a and r1/r2 vectors, so they have the same size:
> a=[1;2;3];
> a=a(:,ones(1,M));
> r1=[0 3 2];
> r1=r1(ones(1,N),:);
> r2=[2 4 3];
> r2=r2(ones(1,N),:);
> nums = sparse( a>r1 & a<r2 )
> nums =
> 1 0 0
> 0 0 0
> 0 0 0
> The questions are:
> How can I obtain nums NxM matrix without allocation cloned matricies a, r1, r2? I'm asking that because this("cloned") matricies are using lot of memory(more than 90% comparig to all other variables), so with fine a mesh I reach "out of memory" message.
> Is there any way to speedup relational operations, allocating result sparse matix?
>
> For clarity, I will describe my problem: I have some distribution of "zones"
> http://homepage.corbina.net/~skarelin/zone_distr.png
> start and end angle of each zone represented in r1 and r2 vectors. And a vector contains angles(computed on some x y z mesh). I need to know for each a element which zones belong to this angle.

a=[2 2 3
    5 6 2
    1 2 3
    1 4 9];
r1=[0 3 2];
r2=[2 5 8];
aa=size(a);
r=zeros(aa);
for t=1:aa(1)
[row,col,v] = find((a(t,:)>r1(1,:)) & (a(t,:)<r2(1,:)));
r(t,col)=1;
end
r

Subject: Determine whether the number is in a given range

From: Jos (10584)

Date: 21 Jan, 2011 15:32:06

Message: 3 of 6

"m4 Chrennikov" <abrek77@gmail.com> wrote in message <ihc5j8$bie$1@fred.mathworks.com>...
> Hi all.
> I want to check if numbers are in a given range. Range represented with 2 other matricies, one for first value of the range other for second. For ex:
> a=[1 2 3];
> r1=[0 3 2];
> r2=[2 4 3];
> now I'm doing something like that
> nums = sparse( a>r1 & a<r2 )
> nums =
> 1 0 0
> Is there more efficient way to do that?
> Actually vector a is Nx1 and vectors r1 & r2 are both 1xM. And result matrix nums should be NxM. Now I clone both a and r1/r2 vectors, so they have the same size:
> a=[1;2;3];
> a=a(:,ones(1,M));
> r1=[0 3 2];
> r1=r1(ones(1,N),:);
> r2=[2 4 3];
> r2=r2(ones(1,N),:);
> nums = sparse( a>r1 & a<r2 )
> nums =
> 1 0 0
> 0 0 0
> 0 0 0
> The questions are:
> How can I obtain nums NxM matrix without allocation cloned matricies a, r1, r2? I'm asking that because this("cloned") matricies are using lot of memory(more than 90% comparig to all other variables), so with fine a mesh I reach "out of memory" message.
> Is there any way to speedup relational operations, allocating result sparse matix?
>
> For clarity, I will describe my problem: I have some distribution of "zones"
> http://homepage.corbina.net/~skarelin/zone_distr.png
> start and end angle of each zone represented in r1 and r2 vectors. And a vector contains angles(computed on some x y z mesh). I need to know for each a element which zones belong to this angle.

I am not sure if I understand your problem correctly but here is an approach for starters:


a = [1 2 3] ;
r1 = [0 1 2] ;
r2 = [2 4 3] ;
q1 = bsxfun(@gt,a(:),r1(:).')
q2 = bsxfun(@lt,a(:),r2(:).')
R = q1 & q2

I am not sure if you can benefit from using sparse, except for the final storage of R

hth
Jos

Subject: Determine whether the number is in a given range

From: m4 Chrennikov

Date: 15 Feb, 2011 13:45:05

Message: 4 of 6

"Jos (10584)" wrote in message <ihc8tm$lgl$1@fred.mathworks.com>...
> I am not sure if I understand your problem correctly but here is an approach for starters:
>
>
> a = [1 2 3] ;
> r1 = [0 1 2] ;
> r2 = [2 4 3] ;
> q1 = bsxfun(@gt,a(:),r1(:).')
> q2 = bsxfun(@lt,a(:),r2(:).')
> R = q1 & q2
>
> I am not sure if you can benefit from using sparse, except for the final storage of R
>
> hth
> Jos
That's what I needed, thanks. Now my code looks like this:

nums = sparse(bsxfun(@ge,fi,fd1) & bsxfun(@le,fi,fd2));

Typical sizes are:
fi ~2e5 x 1 elements
fd1, fd2 1 x ~1e2 elements
number of non zero elements in nums ~2e5
So I can benefit using sparse, due to lower memory usage.
However, this line spends 44% of CPU time. Can you share the next approach (not-for-starters)? :-)

Subject: Determine whether the number is in a given range

From: Jan Simon

Date: 15 Feb, 2011 14:34:05

Message: 5 of 6

Dear m4 Chrennikov,

> nums = sparse(bsxfun(@ge,fi,fd1) & bsxfun(@le,fi,fd2));
> Typical sizes are:
> fi ~2e5 x 1 elements
> fd1, fd2 1 x ~1e2 elements
> number of non zero elements in nums ~2e5

Is fd1 or fd2 sorted? If you have checked, that an element of fi is smaller than 1, you do not have to check for smaller than 2, 3, ... anymore.
And if an element of fi does not match ge(fd1), you do not have to check for le(fd2) anymore.
Both methods can be easily implemented in a C-Mex and reduce the processing time and memory usage remarkably.

Kind regards, Jan

Subject: Determine whether the number is in a given range

From: m4 Chrennikov

Date: 14 Mar, 2011 13:30:21

Message: 6 of 6

"Jan Simon" wrote in message <ije2st$63c$1@fred.mathworks.com>...
> Dear m4 Chrennikov,
>
> > nums = sparse(bsxfun(@ge,fi,fd1) & bsxfun(@le,fi,fd2));
> > Typical sizes are:
> > fi ~2e5 x 1 elements
> > fd1, fd2 1 x ~1e2 elements
> > number of non zero elements in nums ~2e5
>
> Is fd1 or fd2 sorted? If you have checked, that an element of fi is smaller than 1, you do not have to check for smaller than 2, 3, ... anymore.
> And if an element of fi does not match ge(fd1), you do not have to check for le(fd2) anymore.
> Both methods can be easily implemented in a C-Mex and reduce the processing time and memory usage remarkably.
>
> Kind regards, Jan
fd1 & fd2 are not sorted.
I've implemented this line

nums = sparse(bsxfun(@ge,fi,fd1) & bsxfun(@le,fi,fd2));

in a C-mex function. And got 2-x time reduce. Can I call that remarkable?)
Here is my C-code:

#include <math.h>
#include "mex.h"

void mexFunction(int nlhs, mxArray *plhs[], int nrhs, const mxArray *prhs[])
{
    /* Macros for the ouput and input arguments */
    #define NUMS_OUT plhs[0]
    #define FI_IN prhs[0]
    #define FI1_IN prhs[1]
    #define FI2_IN prhs[2]
            
    double *FI, *FI1, *FI2;
    bool *NUMS;
    int M, N;
    int NZmax;
    mwIndex *irs, *jcs, k, n;
    
    M = (int)mxGetM(FI_IN);
    N = (int)mxGetN(FI1_IN);
    FI = mxGetPr(FI_IN);
    FI1 = mxGetPr(FI1_IN);
    FI2 = mxGetPr(FI2_IN);
    
    NZmax = M*(1 + (int)(N > 1));
    
    NUMS_OUT = mxCreateSparseLogicalMatrix(M, N, NZmax);
    NUMS = mxGetData(NUMS_OUT);
    irs = mxGetIr(NUMS_OUT);
    jcs = mxGetJc(NUMS_OUT);
    
    k = 0;
    for(n = 0; n < N; n++)
    {
        mwIndex m;
        jcs[n] = k;
        for(m = 0; m < M; m++)
        {
            if (FI[m] >= FI1[n])
            {
                if (FI[m] <= FI2[n])
                {
                    NUMS[k] = true;
                    irs[k] = m;
                    k++;
                }
            }
        }
    }
    jcs[N] = k;
    
    return;
}

It has at least one vulnerability and i know about it :-) Thanks a lot for help, writing C-mex functions is an intresting way to boost perf.

Can you commet on this code, and give me some advices?

Tags for this Thread

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us