0

I want my code to run faster and this section seems like its making the code run slower.

I tried to vectorize it and use meshgrid but couldn't figure it out.

%generate all noma node combinations with packets
combinations_withpackets=[];
for i=1:N
    for j=1:N
        if(i~=j)
           for k=1:N
               if((k~=i)&&(k~=j))
                   if((packets(i,j)>0)&&(packets(i,k)>0))   
                       combinations_withpackets=[combinations_withpackets;i j k];
                   end
               end
           end
        end
    end
end

This is supposed to create an array of the form [i j k] where i, j and k are nodes, and at each row of the array they are not equal to each other.

It adds an [i j k] combination to combinations_withpackets if there are packets from node i to j and node i to k.

Wolfie
  • 27,562
  • 7
  • 28
  • 55
melodym
  • 1
  • 2
    A [mcve] example would help here, with sample variables. – Ander Biguri Feb 05 '19 at 10:50
  • 2
    An `if` directly inside another `if` is a bit elaborate, one could simply use an `&&` operator in the first declaration. Otherwise, please show what you did with `meshgrid` and why that didn't work. Why this is slow is mainly because you do not initialise `combinations_withpackets`, which is very, very slow in MATLAB, read [this question](https://stackoverflow.com/q/48351041/5211833). So don't initialise and empty array and grow it, instead, preallocate with the correct (or maximum) size and trim afterwards if necessary. That'll save you 99% of the time is my hunch. – Adriaan Feb 05 '19 at 10:50
  • Plus, for a large N, this will be slow, as its approximately O(N^3). – Ander Biguri Feb 05 '19 at 10:52
  • 1
    Consider replacing `combinations_withpackets=[combinations_withpackets;i j k];` with `combinations_withpackets(end+1,:)=[i j k];` – Mefitico Feb 05 '19 at 12:29

1 Answers1

2

If I create a random matrix packets:

N       = 50                %size of the packets matrice
packets = round(rand(N,N)); %random matrice
comb    = nchoosek(1:N,3);  %all combination without permutation
combrow = perms(1:3);       %permutation for dimension 3
comb    = reshape(comb(:,combrow),[],3); %all combination with permutation
f1      = find(packets(sub2ind([N,N],comb(:,1),comb(:,2)))>0); %check condition 1
f2      = find(packets(sub2ind([N,N],comb(:,1),comb(:,3)))>0); %check condition 2
ind     = ismember(f1,f2); %check condition 1&&2
cwp     = comb(f1(ind),:);   %get the result

It should be way faster than the for loop solution.

This algorithm produce (N-2)*(N-1)*(N) combinations (as explained by Ander Biguri, it's almost O(N^3)), so for big N it will consume a lot of memory.

obchardon
  • 10,614
  • 1
  • 17
  • 33