vectorization and matlab functions for multiple for loops and conditionals within

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.

 %linkswithpackets in node matrix form
            l=1;
            packets=zeros(N,N);
            for m=1:N
                for n=1:N
                    packets(m,n)=linkswithpacket(l);
                    l=l+1;
                end
            end


            %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 and 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.

Answer 1

[Aashray]

Hello Ezgi,

I understand that you are trying to find the tuple (i, j, k) such that all three nodes are unique and number of packets sent from node “i" to node “j” and node “i” to node “k” are non-zero.

The slow speed is the result of three nested for loops present in the code which leads to O(N^3) time complexity.

You may follow the below vectorization steps for reducing the execution time:

General Initializations:

N = 30;  
linkswithpacket = randi([0,1], 1, N*N);  

Vectorization:

tic  
l = 1;  
packets = reshape(linkswithpacket, N, N)'; % Creating a sample input  
[i, j, k] = ndgrid(1:N, 1:N, 1:N); % Each point in the 3-D grid returned represents a possible combination of i, j and k (nodes in this case).  

% Creating logical masks  
mask_diff_ij = (i ~= j);  
mask_diff_ik = (i ~= k);  
mask_diff_jk = (j ~= k);  
mask_packets = (packets(sub2ind([N, N], i, j)) > 0) & (packets(sub2ind([N, N], i, k)) > 0); % function fub2ind is used for mapping the 3D indexes (from i,j,k) to 2D index for “packets”.  

% Combining all masks to create the final mask  
mask = mask_diff_ij & mask_diff_ik & mask_diff_jk & mask_packets;  

% Extracting the valid combinations  
combinations_withpackets2 = [i(mask), j(mask), k(mask)];  
combinations_withpackets2 = sortrows(combinations_withpackets2);  
toc 

Elapsed time is 0.045858 seconds.

Outputs for both the implementations can be compared by sorting the “combinations_withpackets” using “sortrows()” function.

The former time is for the looped implementation, and later one is for vectorized implementation. This reduces the execution time by a factor of 10.

You can refer to the following links for more details on “ndgrid()” and “sub2ind()”:

• https://www.mathworks.com/help/matlab/ref/ndgrid.html
• https://www.mathworks.com/help/matlab/ref/sub2ind.html

Also, you may find these MATLAB answers helpful, attaching them for reference:

• https://www.mathworks.com/matlabcentral/answers/398856-improving-the-performance-of-vectorized-code-possible
• https://www.mathworks.com/matlabcentral/answers/301008-vectorized-code-slower-than-loops