how I can change this multi-loop to reduce the computation time in Matlab?

how I can change this multi-loop to reduce the computation time?

A is a matrix (5x10000) with the fifth line contains values between 1 and 50 corresponding to different events of an experiment. My goal is to find the columns of the matrix which are the same for all possible combinations of 7 different events.

      data = A(1:4,:);
      exptEvents = A(5,:);

      % Find repeats
      [b,i,j] = unique(data', 'rows');

      % Organize the indices of the repeated columns into a cell array
      reps = arrayfun(@(x) find(j==x), 1:length(i), 'UniformOutput', false);

      % Find events corresponding to these repeats
      reps_Events = cellfun(@(x) exptEvents(x), reps, 'UniformOutput', false);

      U = cellfun(@unique, reps_Events, 'UniformOutput', false);
      repeat_counts = cellfun(@length, U);

      kk=1;

      for i1=1:50
          for i2=1:50 
              for i3=1:50 
                  for i4=1:50
                      for i5=1:50
                          for i6=1:50
                              for i7=1:50
                                  if i1~=i2 && i2~=i3 && i3~=i4 && i4~=i5 && i5~=i6 && i6~=i7   
                                     myEvents = [i1 i2 i3 i4 i5 i6 i7];
                                     v= b(cellfun(@(x)all(ismember(myEvents,x)),U),:);
                                     intersection(1,kk)=v(1);
                                     intersection(2,kk)=v(2);
                                     intersection(3,kk)=v(3);
                                     intersection(4,kk)=v(4);
                                     intersection(5,kk)=i1;
                                     intersection(6,kk)=i2;
                                     intersection(7,kk)=i3;
                                     intersection(8,kk)=i4;
                                     intersection(9,kk)=i5;
                                     intersection(10,kk)=i6;
                                     intersection(11,kk)=i7;
                                     kk=kk+1;
                                  end
                              end
                          end
                      end
                  end
              end
          end
      end

Answer 1

[Robert Cumming]

have you preallocated the variable intersection?

If not doing that will speed it up.

The other thuing to do is to use the profiler to detect exactly where the time is taken.

[bzak]

I can not know the value of the second dimension of the variable intersection. I think it's the for loops that pose a serious problem.

[Jan]

@bzak: A missing pre-allocation causes an exponentially growing runtime. "Exponential" means: This problem will exceed any other problem, which have a linear runtime behaviour, even if it is extremly slow. Conclusion: Always pre-allocate. If you do not know the size, pre-allocate too much and cut if afterwards. This does not matter -as said already- compared with exponential growing.

[Robert Cumming]

As already stated pre-allocation is vital - you will be amazed at the different - try it for one case where you know the size...

In your instance where at run time you dont know the size you have 2 options.

1. Preallocate bigger than you will ever need.

2. Have a group of for loops which all it does is deterine the size of the matrix - then have your loop above. It WILL be faster than not preallocating.

Answer 2

[Jan]

The case "i1~=i2" is excluded in the innermost loop. So for "i1==i2" all but the first loop waste time only. So better move the exlusing of equal indices to where it has the larges impact.

data = A(1:4,:);
exptEvents = A(5,:);

% Find repeats
[b,i,j] = unique(data', 'rows');

% Organize the indices of the repeated columns into a cell array
reps = arrayfun(@(x) find(j==x), 1:length(i), 'UniformOutput', false);

% Find events corresponding to these repeats
reps_Events = cellfun(@(x) exptEvents(x), reps, 'UniformOutput', false);

U = cellfun(@unique, reps_Events, 'UniformOutput', false);
repeat_counts = cellfun(@length, U);
kk=1;

for i1=1:50
   for i2=1:50
      if i1==i2
         conintue;
      end 
      for i3=1:50
         if i2==i3
            continue;
         end
         for i4=1:50
            if i3==i4
               continue;
            end
            for i5=1:50
               if i4==i5
                  continue;
               end
               for i6=1:50
                  if i5==i6
                     continue;
                  end
                  for i7=1:50
                     if i6~=i7   
                        myEvents = [i1 i2 i3 i4 i5 i6 i7];
                        v= b(cellfun(@(x)all(ismember(myEvents,x)),U),:);
                        intersection(1,kk)=v(1);
                        intersection(2,kk)=v(2);
                        intersection(3,kk)=v(3);
                        intersection(4,kk)=v(4);
                        intersection(5,kk)=i1;
                        intersection(6,kk)=i2;
                        intersection(7,kk)=i3;
                        intersection(8,kk)=i4;
                        intersection(9,kk)=i5;
                        intersection(10,kk)=i6;
                        intersection(11,kk)=i7;
                        kk=kk+1;
                     end
                  end
               end
            end
         end
      end
   end
end

But now let's come to the real problem:_The pre-allocation. intersection is increased 49^7 times (correct?). You need 11 elements with 8 bytes per DOUBLE. Do I see this correctly that this requires 68.8 TB? Das this match in your RAM? And without a pre-allocation the array must be allocated repeatedly. This means a magnitude of prod(1:49^7)=prod(1:6.7822e+011) allocated bytes. Matlab claims, that this is Inf, but this is exaggerated.

If you have enough RAM and pre-allocate, there is another problem: Assuming you can process 1000 iterations per second, this total computing time would be about 2.1 years.

I think v=b(cellfun(@(x)all(ismember(myEvents,x)),U),:) is not efficient. But after the above arguments, I do not investigate this.