decreasing run time of a program -

Hi all;

I've written a program including foure loops like below:

clear ; clc ; tic ;
%== input data ================================================

cap= 30;
T=3;
q=[0,10,20; 40,50,60; 10,20,30;] ;
pr=ones(3)*0.33;
s=[0;10;20;30];
r=[10;20;30;40];
nq=size(q,2);
ns=length(s);
nr=length(r);
ts=20;
tr=25;

% THE MAIN PART OF PROGRAM WHICH MUST BE VECTORISED : the part
% below up to "n=n+1" line, must be vectorised using ommiting all 
% three loops i.e "ss" , "qq", "rr"  

n=1;
while n<10000
    for  t=T:-1:1
        for ss=1:ns
            for  qq=1:nq
                for rr=1:nr
                 s2{t,ss}(qq,rr)= s(ss)+q(t,qq)-r(rr);
                  if  s2{t,ss}(qq,rr)<=cap &&  s2{t,ss}(qq,rr)>=0
                   tsd{t,ss}(qq,rr)=(ts-s(ss))^2+ (tr- r(rr))^2 ;
                  else
                    s2{t,ss}(qq,rr)=NaN;  tsd{t,ss}(qq,rr)=NaN;
                  end

                   if n==1 && t==T
                      tsd_total{n,ss}(qq,rr)=tsd{t,ss}(qq,rr);
                   else
                      if  s2{t,ss}(qq,rr)>=0
                         for kk=1:ns
                      if  s2{t,ss}(qq,rr)==s(kk);
  tsd_total{n,ss}(qq,rr)=tsd{t,ss}(qq,rr)+ pr(qq,:)*f_min{n-1,kk}(:,1);
    end
       end;
          else;
            tsd_total{n,ss}(qq,rr)=NaN ;
            end
            end
          end
      f_min{n,ss}(qq,1)= min(tsd_total{n,ss}(qq,:));
          end
          end
          n=n+1;
      end

%= below lines are criterias to stop program ==========

      y_brk1=0;
      if n>3*T
          nT=fix(n/T);
          for p=T:nT+1
              if (n-1)==(p-1)*T;
                  c1 =(p-T-1)*T; c2=(p-T)*T; c3 =(p+1-T)*T;
                  f_1=cell2mat(tsd_total(c1+1:c2,:));
                  f_2=cell2mat(tsd_total(c2+1:c3,:));
                  f_3=cell2mat(tsd_total(c3+1:n-1,:));
                  dif_32=fix(f_3-f_2);
                  dif_21=fix(f_2-f_1);
if isequalwithequalnans(dif_32,dif_21)==1  ;   y_brk1=1; end
              end
              if y_brk1==1; break;  end
          end
      end
      if y_brk1==1; break; end
  end
  toc        end
      end
      if y_brk1==1; break; end
  end
  toc

sine s, r and q are predetemind in the form of inputs, their relevant loops i.e. 'ss', ' qq'and 'rr' can be removed from the program. this deletion make my program so faster in run especially when the dimension of s, r and q are big.

I've tried to remove 'rr' and 'qq' loops by following programe, but I need to remove "ss loop" as well. how can I do this?? Any help would be appreciated a lot.

    clear  ;  clc; tic ;

    %===== DATA ==============

    s_max= 30;
    s_min=0;
    T=3;
    q=[0,10,20; 40,50,60; 10,20,30;] ;
    pr=ones(3)*0.33;
    s=[0;10;20;30];
    r=[10,20,30,40;];
    nq=size(q,2);
    ns=length(s);
    nr=length(r);
    ts=20;
    tr=25;

    % PREALLOCATION OF VARIABLES =========

    s2=cell(T,ns);
    tsd=s2;
    r_opt =cell(big_num,ns);;
    tsd_total=r_opt;
    fmin_init=cell(big_num,1);
    tsd_intrpln=cell(big_num,nq);

    %THE MAIN PART OF PROGRAM WHICH WAS VECTORISED====== 

    dr= bsxfun(@minus,r,ones(nq,nr).*tr).^2;
    n=1;
    while n<10000
        fmin_init{n}=ones(ns,nq);
        for  t=T:-1:1
            sum_qr= bsxfun(@minus,q(t,:)',r);
            for ss=1:ns
                tsd_total{n,ss}=ones(nq,nr)*888888 ;
                r_opt{n,ss}=ones(nq,nr)*888888 ;

                sum_qrs=s(ss)+ sum_qr;
                s2_orgnl{t,ss}=sum_qrs;

                ds=bsxfun(@minus,s(ss)*ones(nq,nr),ts).^2;
                tsd_init=bsxfun(@plus, ds,dr);

                index_out = sum_qrs>s_max  | sum_qrs <s_min;
                sum_qrs(index_out)=NaN;
                tsd_init(index_out)= NaN;
                s2{t,ss}= sum_qrs;
                tsd{t,ss}=tsd_init;

                if n==1 && t==T
                    tsd_total{n,ss}=tsd{t,ss};
                else
                    sum=0;
                    for qq=1:nq
 tsd_intrpln{n,qq}=ones(nq,nr) ;
 tsd_intrpln{n,qq}=interp1(s(:),fmin_init{n-1}(:,qq), s2{t,ss},'nearest');
sum = sum+pr(t,qq) .*tsd_intrpln{n,qq};
   end
                    tsd_total{n,ss}=sum + tsd{t,ss};
                end
                f_min{n,ss}= min(tsd_total{n,ss},[],2);
                fmin_init_0{n,ss}= f_min{n,ss}';
            end
            fmin_init_1{n}= cell2mat(fmin_init_0(n,:));
            fmin_init{n} = vec2mat(fmin_init_1{n},nq );
            n=n+1;
        end

    %= below lines are criterias to stop program =

        y_brk1=0;

        if n>3*T
            nT=fix(n/T);
            for p=T:nT+1
                if (n-1)==(p-1)*T;
                    c1 =(p-T-1)*T; c2=(p-T)*T; c3 =(p+1-T)*T;
                    f_1=cell2mat(tsd_total(c1+1:c2,:));
                    f_2=cell2mat(tsd_total(c2+1:c3,:));
                    f_3=cell2mat(tsd_total(c3+1:n-1,:));
                    dif_32=fix(f_3-f_2);
                    dif_21=fix(f_2-f_1);
 if isequalwithequalnans(dif_32,dif_21)==1  ;   y_brk1=1; end
                end
                if y_brk1==1; break;  end
            end
        end
        if y_brk1==1; break; end
    end
    toc

Any help would really be appropriated.

Answer 1

[Jan]

You do not need BSXFUN for operations with scalars:

bsxfun(@minus, r,ones(nq, nr) .* tr) .^ 2

==> faster:

(r - tr) .^ 2

interp1 is very slow in Matlab. You can copy the code o INTERP1 and crop all unnecessary tests and branches.

The repeated multiplication "ones(nq,nr)*888888" wastes time. repmat(888888, nq, nr) would be faster. But "888888" looks like a magic number - an ugly anti-pattern of bad programming practice.

A faster breaking out of the loop:

y_brk1 = 0;
for p=T:nT+1
  if (n-1)==(p-1)*T;
    ...
    if isequalwithequalnans(dif_32,dif_21)  % no "== 1"
      y_brk1 = 1;
      break;  % Break out of "for p"
    end
 end

So before vectorizing, there is a lot of potential for accelerations in the loop methods already.

[som]

Thanks for your constructive comments.

As you are an expert in Matlab, Can I ask you to spend time for understanding whole of the program? I know its time consuming for you , but I 'm sure you can help me to resolve problems about my program's run time.

Thanks in advance