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:
looking for faster way to build a big cell

Subject: looking for faster way to build a big cell

From: WK

Date: 15 Jul, 2013 07:07:10

Message: 1 of 10

hi all,
  I am looking for a faster way to generate a cell matrix. In my program, I have a big matrix called MT of 10000x10000. There is another 1D vector X of 1x5000. For each element of X, I am searching all element indices of MT such that the element is within +/- 0.5 around the current element of X. Here is what I did

for n=1:5000
  P{n} = find( (MT>=X(n)-0.5) & (MT<=X(n)+0.5) );
end

this loop is pretty slow. Is that any way to boost the code or achieve the same thing without using the loop? Thanks.

Subject: looking for faster way to build a big cell

From: Nasser M. Abbasi

Date: 15 Jul, 2013 09:10:21

Message: 2 of 10

On 7/15/2013 2:07 AM, WK wrote:
> hi all,
> I am looking for a faster way to generate a cell matrix. In my program,
>I have a big matrix called MT of 10000x10000. There is another 1D vector
>X of 1x5000. For each element of X, I am searching all element indices of
> MT such that the element is within +/- 0.5 around the current element of X. Here is what I did
>
> for n=1:5000
> P{n} = find( (MT>=X(n)-0.5) & (MT<=X(n)+0.5) );
> end
>
> this loop is pretty slow. Is that any way to boost the code or
>achieve the same thing without using the loop? Thanks.
>

One thing you can try is reduce the amount of allocation inside
the find by combining the test into one instead of two.

for n=1:N
   P{n}=find( abs(MT-X(n))<=0.5 );
end


For example:
-------------------------
clear all
MT=rand(5000);
N=50;
X=rand(N,1);

tic;
for n=1:N
   P{n}=find( abs(MT-X(n))<0.1 );
end
t=toc;
fprintf('using abs check, time used = %f\n',t);
clear P;

tic;
for n=1:N
   Z{n}=find( (MT>=(X(n)-0.1)) & (MT<=(X(n)+0.1)) );
end
t=toc;
fprintf('using double checks, time used = %f\n',t);
-------------------------

using abs check, time used = 7.053266
using double checks, time used = 22.197705


There might be other things to do to speed it up.

--Nasser

Subject: looking for faster way to build a big cell

From: WK

Date: 15 Jul, 2013 12:59:10

Message: 3 of 10

Hi Nasser,
  It is a really good idea. But I just find that it only works to the case when the comparison statement is >= and <=, but it fail if I change my statement to >= and <, but your solution to the first case works. I am still looking the faster scheme for the second case :)

"Nasser M. Abbasi" wrote in message <ks0e9r$rqu$1@speranza.aioe.org>...
> On 7/15/2013 2:07 AM, WK wrote:
> > hi all,
> > I am looking for a faster way to generate a cell matrix. In my program,
> >I have a big matrix called MT of 10000x10000. There is another 1D vector
> >X of 1x5000. For each element of X, I am searching all element indices of
> > MT such that the element is within +/- 0.5 around the current element of X. Here is what I did
> >
> > for n=1:5000
> > P{n} = find( (MT>=X(n)-0.5) & (MT<=X(n)+0.5) );
> > end
> >
> > this loop is pretty slow. Is that any way to boost the code or
> >achieve the same thing without using the loop? Thanks.
> >
>
> One thing you can try is reduce the amount of allocation inside
> the find by combining the test into one instead of two.
>
> for n=1:N
> P{n}=find( abs(MT-X(n))<=0.5 );
> end
>
>
> For example:
> -------------------------
> clear all
> MT=rand(5000);
> N=50;
> X=rand(N,1);
>
> tic;
> for n=1:N
> P{n}=find( abs(MT-X(n))<0.1 );
> end
> t=toc;
> fprintf('using abs check, time used = %f\n',t);
> clear P;
>
> tic;
> for n=1:N
> Z{n}=find( (MT>=(X(n)-0.1)) & (MT<=(X(n)+0.1)) );
> end
> t=toc;
> fprintf('using double checks, time used = %f\n',t);
> -------------------------
>
> using abs check, time used = 7.053266
> using double checks, time used = 22.197705
>
>
> There might be other things to do to speed it up.
>
> --Nasser

Subject: looking for faster way to build a big cell

From: James Tursa

Date: 15 Jul, 2013 18:26:09

Message: 4 of 10

"Nasser M. Abbasi" wrote in message <ks0e9r$rqu$1@speranza.aioe.org>...
> On 7/15/2013 2:07 AM, WK wrote:
> > hi all,
> > I am looking for a faster way to generate a cell matrix. In my program,
> >I have a big matrix called MT of 10000x10000. There is another 1D vector
> >X of 1x5000. For each element of X, I am searching all element indices of
> > MT such that the element is within +/- 0.5 around the current element of X. Here is what I did
> >
> > for n=1:5000
> > P{n} = find( (MT>=X(n)-0.5) & (MT<=X(n)+0.5) );
> > end
> >
> > this loop is pretty slow. Is that any way to boost the code or
> >achieve the same thing without using the loop? Thanks.
> >
>
> One thing you can try is reduce the amount of allocation inside
> the find by combining the test into one instead of two.
>
> for n=1:N
> P{n}=find( abs(MT-X(n))<=0.5 );
> end
>
>
> For example:
> -------------------------
> clear all
> MT=rand(5000);
> N=50;
> X=rand(N,1);
>
> tic;
> for n=1:N
> P{n}=find( abs(MT-X(n))<0.1 );
> end
> t=toc;
> fprintf('using abs check, time used = %f\n',t);
> clear P;
>
> tic;
> for n=1:N
> Z{n}=find( (MT>=(X(n)-0.1)) & (MT<=(X(n)+0.1)) );
> end
> t=toc;
> fprintf('using double checks, time used = %f\n',t);
> -------------------------
>
> using abs check, time used = 7.053266
> using double checks, time used = 22.197705
>
>
> There might be other things to do to speed it up.
>
> --Nasser

Not sure it will make a significant difference to the timing, but you should pre-allocate the cell array result. e.g.,

P = cell(N,1);
    :
Z = cell(N,1);

James Tursa

Subject: looking for faster way to build a big cell

From: James Tursa

Date: 15 Jul, 2013 18:31:10

Message: 5 of 10

"WK" wrote in message <ks0rmu$2uu$1@newscl01ah.mathworks.com>...
> Hi Nasser,
> It is a really good idea. But I just find that it only works to the case when the comparison statement is >= and <=, but it fail if I change my statement to >= and <, but your solution to the first case works. I am still looking the faster scheme for the second case :)

Depending on how desperate you are for speed, you could resort to a mex routine for this. That way you can control how the data gets dragged though the high level cache and the exact comparisons you want to make < vs <= vs > vs >=.

James Tursa

Subject: looking for faster way to build a big cell

From: WK

Date: 15 Jul, 2013 18:45:10

Message: 6 of 10

Thanks James. It helps a bit but not much. I try the cell function with

ffun = @(n) find( (MT>=X(n)-0.5) & (MT<=X(n)+0.5) );
P = cellfun(ffun, num2cell(1:N), , 'UniformOutput', false);

it helps. But it still kinda slow since I am dealing a big matrix. I found that the reason causing the slow performance is the way to generate MT. MT is generated as follows

[u, v] = meshgrid([-1:0.001:1, -1000,1000]);
MT = u+v;

but the matrix is too big. I don't know if there is any other way to achieve the same purpose but with less memory occupied.

"James Tursa" wrote in message <ks1es1$rj2$1@newscl01ah.mathworks.com>...
> "Nasser M. Abbasi" wrote in message <ks0e9r$rqu$1@speranza.aioe.org>...
> > On 7/15/2013 2:07 AM, WK wrote:
> > > hi all,
> > > I am looking for a faster way to generate a cell matrix. In my program,
> > >I have a big matrix called MT of 10000x10000. There is another 1D vector
> > >X of 1x5000. For each element of X, I am searching all element indices of
> > > MT such that the element is within +/- 0.5 around the current element of X. Here is what I did
> > >
> > > for n=1:5000
> > > P{n} = find( (MT>=X(n)-0.5) & (MT<=X(n)+0.5) );
> > > end
> > >
> > > this loop is pretty slow. Is that any way to boost the code or
> > >achieve the same thing without using the loop? Thanks.
> > >
> >
> > One thing you can try is reduce the amount of allocation inside
> > the find by combining the test into one instead of two.
> >
> > for n=1:N
> > P{n}=find( abs(MT-X(n))<=0.5 );
> > end
> >
> >
> > For example:
> > -------------------------
> > clear all
> > MT=rand(5000);
> > N=50;
> > X=rand(N,1);
> >
> > tic;
> > for n=1:N
> > P{n}=find( abs(MT-X(n))<0.1 );
> > end
> > t=toc;
> > fprintf('using abs check, time used = %f\n',t);
> > clear P;
> >
> > tic;
> > for n=1:N
> > Z{n}=find( (MT>=(X(n)-0.1)) & (MT<=(X(n)+0.1)) );
> > end
> > t=toc;
> > fprintf('using double checks, time used = %f\n',t);
> > -------------------------
> >
> > using abs check, time used = 7.053266
> > using double checks, time used = 22.197705
> >
> >
> > There might be other things to do to speed it up.
> >
> > --Nasser
>
> Not sure it will make a significant difference to the timing, but you should pre-allocate the cell array result. e.g.,
>
> P = cell(N,1);
> :
> Z = cell(N,1);
>
> James Tursa

Subject: looking for faster way to build a big cell

From: WK

Date: 15 Jul, 2013 19:06:12

Message: 7 of 10

Hi James,
  I has no experience in working with mex, any example for me to follow? Thanks.
"James Tursa" wrote in message <ks1f5e$saa$1@newscl01ah.mathworks.com>...
> "WK" wrote in message <ks0rmu$2uu$1@newscl01ah.mathworks.com>...
> > Hi Nasser,
> > It is a really good idea. But I just find that it only works to the case when the comparison statement is >= and <=, but it fail if I change my statement to >= and <, but your solution to the first case works. I am still looking the faster scheme for the second case :)
>
> Depending on how desperate you are for speed, you could resort to a mex routine for this. That way you can control how the data gets dragged though the high level cache and the exact comparisons you want to make < vs <= vs > vs >=.
>
> James Tursa

Subject: looking for faster way to build a big cell

From: dpb

Date: 16 Jul, 2013 00:38:40

Message: 8 of 10

On 7/15/2013 1:45 PM, WK wrote:

...Do NOT TOPPOST!!! PLEASE!!!...

> Thanks James. It helps a bit but not much. I try the cell function with
> ffun = @(n) find( (MT>=X(n)-0.5) & (MT<=X(n)+0.5) );
> P = cellfun(ffun, num2cell(1:N), , 'UniformOutput', false);
>
> it helps. But it still kinda slow since I am dealing a big matrix. I
...

>
> but the matrix is too big. I don't know if there is any other way to
> achieve the same purpose but with less memory occupied.
...

I'm thinking accumarray() ... altho I don't have time to play just now I
did learn a new trick just a couple of days ago w/ it. It's still too
new (to me, the "trick", that is) that I can't write it right w/o
stopping and working it out--it has to do w/ the SZ argument which is
indecipherable nearly from the doc's...

--

Subject: looking for faster way to build a big cell

From: dpb

Date: 16 Jul, 2013 01:01:15

Message: 9 of 10

On 7/15/2013 7:38 PM, dpb wrote:
> On 7/15/2013 1:45 PM, WK wrote:
>
> ...Do NOT TOPPOST!!! PLEASE!!!...
>
...

>> it helps. But it still kinda slow since I am dealing a big matrix. I
> ...
>
>>
>> but the matrix is too big. I don't know if there is any other way to
>> achieve the same purpose but with less memory occupied.
> ...
>
> I'm thinking accumarray() ... altho I don't have time to play just now I
> did learn a new trick just a couple of days ago w/ it....

OK, try this--I've done no timing; only the toy example to test.
Obviously you have to modify the anon function to suit...

 >> M=rand(20);
 >> X=rand(4,1);
 >> m=accumarray([1:4]',X,[4 1],@(x) {find(abs(M-x)<0.005)})
m =
     [6x1 double]
     [5x1 double]
     [0x1 double]
     [ 120]
 >> m{:}
ans =
     32
    253
    273
    328
    338
    393
ans =
      7
     24
     47
    333
    345
ans =
    Empty matrix: 0-by-1
ans =
    120
 >> [X(4) M(120) abs(X(4)-M(120))]
ans =
     0.4325 0.4299 0.0026
 >>

NB: Don't forget to encapsulate the function return in curlies to make
the cell array--otherwise accumarry will whine...

--

Subject: looking for faster way to build a big cell

From: dpb

Date: 16 Jul, 2013 01:04:49

Message: 10 of 10

On 7/15/2013 8:01 PM, dpb wrote:
...

> OK, try this--I've done no timing; only the toy example to test.
> Obviously you have to modify the anon function to suit...
>
> >> M=rand(20);
> >> X=rand(4,1);
> >> m=accumarray([1:4]',X,[4 1],@(x) {find(abs(M-x)<0.005)})
...

L=length(X);
m=accumarray([1:L]',X,[L 1],@(x) {find(abs(M-x)<0.005)});

The '4' was just shorthand at command line forgot to remove, sorry...

--

Tags for this Thread

No tags are associated with 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