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:
The old story, for-loops and slow code.. (Sample Entropy)

Subject: The old story, for-loops and slow code.. (Sample Entropy)

From: Aino

Date: 10 Jun, 2010 15:06:04

Message: 1 of 9

Hello all!

I am again struggling with a same problem that I have encountered time and time again with no real luck of solving it: how to speed up my code. Here is a little code than calculates Sample Entropy and the error for it that is basically one for loop in side another (it is also inside several for-loops in the program that calls it..):

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function [SampEnt,Error]=SampEntropy4(cop,M,r)

N=length(cop);
CIM=[];

for m=[M,M+1]
    Cim=NaN(1,N-m);
    
    parfor i=1:N-m
        count=0;
        seg_i=cop(i:i+m-1);
        
        for j=1:N-m
            seg_j=cop(j:j+m-1);
            
            if max(abs(seg_i-seg_j))<r
                count=count+1;
            end
            
        end
        
        Cim(i)=(count-1)/(N-m-1);
        count=0;
    end
    CIM=cat(2,CIM,sum(Cim)/(N-m));
    
end

B=CIM(1)*((N-M-1)*(N-M));
%A=CIM(2)*((N-M-1)*(N-M));
CP=CIM(2)/CIM(1);

SampEnt=-log(CP);

%Error estimation:
KbOneround=2*M-2;%Overlaps with one template of length m (one i segment)
Kb=length(1:N-M)*KbOneround;%Overlaps with all matches with templetes of length m

KaOneround=2*(M+1)-2;
Ka=length(1:N-(M+1))*KaOneround;

sigma=sqrt(CP*(1-CP)/B+1/B^2*(Ka-Kb*CP^2));

Error=max(sigma/CP,sigma/(SampEnt*CP));%Should be<0.05
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

At the moment it takes 22 second to run this code with my computer, when cop=rand(1,1500), M=2 (M is always small) and r=0.2*std(cop). Profiler showed that the line that takes the most time is "if max(abs(seg_i-seg_j))<r", 60% of all time and the second biggest time consumer was "seg_j=cop(j:j+m-1);" with 32% of all time. I calculated that it would take me 10 days to get just the first set of results with this code.. Please help me, the code should take no more than ~5 seconds to run so that I could actually use it!

Here is what I have been thinking:

1) Pre allocation: I believe I have allocated all that I can (basically just Cim, CIM is only used twice). Allocating seg_i and seg_j made no difference.

2)Vectorization: The line "if max(abs(seg_i-seg_j))<r" is in vector form, but I don't see how to do this with the other for-loops. This would probably be the easiest way of speeding up the code, but even though I do get the easy examples about vectorization, I don't see how to put this in the vector form. Is it possible? Could you show me the right direction how to do it?

3) Parfor-loops: As you can see, there is one parfor in my code. It took ~5 s from the time. I hope I have used it correctly. :)

4) Mex-files: The trouble is that it has been years when I last coded anything with C and I have tried this unsuccessfully about three times in the past. Also back then I had some help, now there is a 7 hour time difference between me and my usual support group..

5) Batch: I am not really familiar with using batch, could this be used to save some time? Does this only work with scripts?

6) More computing power: The last resort. Might be an option if all other options fail.

So, thank you for reading this post. Where would you start with this? Is it possible to do little changes to the code or should I just go for Mex-files or computing powers? Is there perhaps some method I haven't thought about?

Thank You,
Aino

  
 

Subject: The old story, for-loops and slow code.. (Sample Entropy)

From: Aino

Date: 10 Jun, 2010 15:32:04

Message: 2 of 9

Ou nou, now I saw there is some "slicing" problem with seg_j.. First time parfor user.. Maybe correcting this would help speed up the code.

-Aino

"Aino" <aino.tietavainen@removeThis.helsinki.fi> wrote in message <huqv0s$aio$1@fred.mathworks.com>...
> Hello all!
>
> I am again struggling with a same problem that I have encountered time and time again with no real luck of solving it: how to speed up my code. Here is a little code than calculates Sample Entropy and the error for it that is basically one for loop in side another (it is also inside several for-loops in the program that calls it..):
>
> %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
> function [SampEnt,Error]=SampEntropy4(cop,M,r)
>
> N=length(cop);
> CIM=[];
>
> for m=[M,M+1]
> Cim=NaN(1,N-m);
>
> parfor i=1:N-m
> count=0;
> seg_i=cop(i:i+m-1);
>
> for j=1:N-m
> seg_j=cop(j:j+m-1);
>
> if max(abs(seg_i-seg_j))<r
> count=count+1;
> end
>
> end
>
> Cim(i)=(count-1)/(N-m-1);
> count=0;
> end
> CIM=cat(2,CIM,sum(Cim)/(N-m));
>
> end
>
> B=CIM(1)*((N-M-1)*(N-M));
> %A=CIM(2)*((N-M-1)*(N-M));
> CP=CIM(2)/CIM(1);
>
> SampEnt=-log(CP);
>
> %Error estimation:
> KbOneround=2*M-2;%Overlaps with one template of length m (one i segment)
> Kb=length(1:N-M)*KbOneround;%Overlaps with all matches with templetes of length m
>
> KaOneround=2*(M+1)-2;
> Ka=length(1:N-(M+1))*KaOneround;
>
> sigma=sqrt(CP*(1-CP)/B+1/B^2*(Ka-Kb*CP^2));
>
> Error=max(sigma/CP,sigma/(SampEnt*CP));%Should be<0.05
> %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
>
> At the moment it takes 22 second to run this code with my computer, when cop=rand(1,1500), M=2 (M is always small) and r=0.2*std(cop). Profiler showed that the line that takes the most time is "if max(abs(seg_i-seg_j))<r", 60% of all time and the second biggest time consumer was "seg_j=cop(j:j+m-1);" with 32% of all time. I calculated that it would take me 10 days to get just the first set of results with this code.. Please help me, the code should take no more than ~5 seconds to run so that I could actually use it!
>
> Here is what I have been thinking:
>
> 1) Pre allocation: I believe I have allocated all that I can (basically just Cim, CIM is only used twice). Allocating seg_i and seg_j made no difference.
>
> 2)Vectorization: The line "if max(abs(seg_i-seg_j))<r" is in vector form, but I don't see how to do this with the other for-loops. This would probably be the easiest way of speeding up the code, but even though I do get the easy examples about vectorization, I don't see how to put this in the vector form. Is it possible? Could you show me the right direction how to do it?
>
> 3) Parfor-loops: As you can see, there is one parfor in my code. It took ~5 s from the time. I hope I have used it correctly. :)
>
> 4) Mex-files: The trouble is that it has been years when I last coded anything with C and I have tried this unsuccessfully about three times in the past. Also back then I had some help, now there is a 7 hour time difference between me and my usual support group..
>
> 5) Batch: I am not really familiar with using batch, could this be used to save some time? Does this only work with scripts?
>
> 6) More computing power: The last resort. Might be an option if all other options fail.
>
> So, thank you for reading this post. Where would you start with this? Is it possible to do little changes to the code or should I just go for Mex-files or computing powers? Is there perhaps some method I haven't thought about?
>
> Thank You,
> Aino
>
>
>

Subject: The old story, for-loops and slow code.. (Sample Entropy)

From: Aino

Date: 10 Jun, 2010 15:43:04

Message: 3 of 9

Ou nou, now I saw there is some "slicing" problem with seg_j.. First time parfor user.. Maybe correcting this would help speed up the code.

-Aino

"Aino" <aino.tietavainen@removeThis.helsinki.fi> wrote in message <huqv0s$aio$1@fred.mathworks.com>...
> Hello all!
>
> I am again struggling with a same problem that I have encountered time and time again with no real luck of solving it: how to speed up my code. Here is a little code than calculates Sample Entropy and the error for it that is basically one for loop in side another (it is also inside several for-loops in the program that calls it..):
>
> %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
> function [SampEnt,Error]=SampEntropy4(cop,M,r)
>
> N=length(cop);
> CIM=[];
>
> for m=[M,M+1]
> Cim=NaN(1,N-m);
>
> parfor i=1:N-m
> count=0;
> seg_i=cop(i:i+m-1);
>
> for j=1:N-m
> seg_j=cop(j:j+m-1);
>
> if max(abs(seg_i-seg_j))<r
> count=count+1;
> end
>
> end
>
> Cim(i)=(count-1)/(N-m-1);
> count=0;
> end
> CIM=cat(2,CIM,sum(Cim)/(N-m));
>
> end
>
> B=CIM(1)*((N-M-1)*(N-M));
> %A=CIM(2)*((N-M-1)*(N-M));
> CP=CIM(2)/CIM(1);
>
> SampEnt=-log(CP);
>
> %Error estimation:
> KbOneround=2*M-2;%Overlaps with one template of length m (one i segment)
> Kb=length(1:N-M)*KbOneround;%Overlaps with all matches with templetes of length m
>
> KaOneround=2*(M+1)-2;
> Ka=length(1:N-(M+1))*KaOneround;
>
> sigma=sqrt(CP*(1-CP)/B+1/B^2*(Ka-Kb*CP^2));
>
> Error=max(sigma/CP,sigma/(SampEnt*CP));%Should be<0.05
> %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
>
> At the moment it takes 22 second to run this code with my computer, when cop=rand(1,1500), M=2 (M is always small) and r=0.2*std(cop). Profiler showed that the line that takes the most time is "if max(abs(seg_i-seg_j))<r", 60% of all time and the second biggest time consumer was "seg_j=cop(j:j+m-1);" with 32% of all time. I calculated that it would take me 10 days to get just the first set of results with this code.. Please help me, the code should take no more than ~5 seconds to run so that I could actually use it!
>
> Here is what I have been thinking:
>
> 1) Pre allocation: I believe I have allocated all that I can (basically just Cim, CIM is only used twice). Allocating seg_i and seg_j made no difference.
>
> 2)Vectorization: The line "if max(abs(seg_i-seg_j))<r" is in vector form, but I don't see how to do this with the other for-loops. This would probably be the easiest way of speeding up the code, but even though I do get the easy examples about vectorization, I don't see how to put this in the vector form. Is it possible? Could you show me the right direction how to do it?
>
> 3) Parfor-loops: As you can see, there is one parfor in my code. It took ~5 s from the time. I hope I have used it correctly. :)
>
> 4) Mex-files: The trouble is that it has been years when I last coded anything with C and I have tried this unsuccessfully about three times in the past. Also back then I had some help, now there is a 7 hour time difference between me and my usual support group..
>
> 5) Batch: I am not really familiar with using batch, could this be used to save some time? Does this only work with scripts?
>
> 6) More computing power: The last resort. Might be an option if all other options fail.
>
> So, thank you for reading this post. Where would you start with this? Is it possible to do little changes to the code or should I just go for Mex-files or computing powers? Is there perhaps some method I haven't thought about?
>
> Thank You,
> Aino
>
>
>

Subject: The old story, for-loops and slow code.. (Sample Entropy)

From: Jan Simon

Date: 10 Jun, 2010 15:56:04

Message: 4 of 9

Dear Aino!

> if max(abs(seg_i-seg_j))<r

You could try to use anyExceed to avoid the explicte creation of the temporary vectors in this line:
  http://www.mathworks.com/matlabcentral/fileexchange/27857

E.g.:
  mr = -r;
  ...
  if anyExceed(seg_i - seg_j, mr, r)

Good luck, Jan

Subject: The old story, for-loops and slow code.. (Sample Entropy)

From: Aino

Date: 10 Jun, 2010 16:34:04

Message: 5 of 9

Dear Jan,

thank you for your help. I tried the anyExceed code, but unfortunately it only slowed my code down. Perhaps this might be different if M would be bigger? I also have to add to my previous post that after putting that parfor the Profiler says that that takes 90% of all time.

I think I'm using the parfor wrong, I cannot figure out how to make that sig_i a sliced variable. All of the sliced variables in the examples I have found have indexing like A(i)=C(...). Mine is sig_i=cop(..).

I don't know where to start..

Best Regards,
Aino

"Jan Simon" <matlab.THIS_YEAR@nMINUSsimon.de> wrote in message <hur1uk$qtl$1@fred.mathworks.com>...
> Dear Aino!
>
> > if max(abs(seg_i-seg_j))<r
>
> You could try to use anyExceed to avoid the explicte creation of the temporary vectors in this line:
> http://www.mathworks.com/matlabcentral/fileexchange/27857
>
> E.g.:
> mr = -r;
> ...
> if anyExceed(seg_i - seg_j, mr, r)
>
> Good luck, Jan

Subject: The old story, for-loops and slow code.. (Sample Entropy)

From: Aino

Date: 10 Jun, 2010 16:44:04

Message: 6 of 9

Dear Jan,

thank you for your help. I tried the code, but unfortunately it only slowed my code. Perhaps because M is so small?

I'm having trouble of converting my seg_i to a sliced variable, could anyone help me with that?

(I seem to have difficulties getting my post trough, I hope this one doesn't come as a double..)

Best Regards,
Aino

"Jan Simon" <matlab.THIS_YEAR@nMINUSsimon.de> wrote in message <hur1uk$qtl$1@fred.mathworks.com>...
> Dear Aino!
>
> > if max(abs(seg_i-seg_j))<r
>
> You could try to use anyExceed to avoid the explicte creation of the temporary vectors in this line:
> http://www.mathworks.com/matlabcentral/fileexchange/27857
>
> E.g.:
> mr = -r;
> ...
> if anyExceed(seg_i - seg_j, mr, r)
>
> Good luck, Jan

Subject: The old story, for-loops and slow code.. (Sample Entropy)

From: Aino

Date: 10 Jun, 2010 17:22:07

Message: 7 of 9

I forgot to type "matlabpool" before I ran the code.. 9s! It is getting closer..

(Does anyone know what to do with the double posts?)

-Aino :)

Subject: The old story, for-loops and slow code.. (Sample Entropy)

From: Oleg Komarov

Date: 10 Jun, 2010 19:01:07

Message: 8 of 9

"Aino" <aino.tietavainen@removeThis.helsinki.fi> wrote in message <hur6vv$42a$1@fred.mathworks.com>...
> I forgot to type "matlabpool" before I ran the code.. 9s! It is getting closer..
>
> (Does anyone know what to do with the double posts?)
>
> -Aino :)

Yes. After posting don't hit the go back button but follow the link.

Other actions would be to write to the admins but I wouldn't bother them for that.

oleg

Subject: The old story, for-loops and slow code.. (Sample Entropy)

From: Aino

Date: 10 Jun, 2010 19:56:06

Message: 9 of 9

Thank you,

will make sure I use the right button (well see soon if that works).

-Aino

"Oleg Komarov" <oleg.komarovRemove.this@hotmail.it> wrote in message <hurcpj$t31$1@fred.mathworks.com>...
> "Aino" <aino.tietavainen@removeThis.helsinki.fi> wrote in message <hur6vv$42a$1@fred.mathworks.com>...
> > I forgot to type "matlabpool" before I ran the code.. 9s! It is getting closer..
> >
> > (Does anyone know what to do with the double posts?)
> >
> > -Aino :)
>
> Yes. After posting don't hit the go back button but follow the link.
>
> Other actions would be to write to the admins but I wouldn't bother them for that.
>
> oleg

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