CODEWITHSUNDEEP
performancematlabvectorization
KiW
KiW

Reputation: 593

Vectorize loop with nested if-clause

Problem

I am trying to optimize the runtime of my code and have asked a similar question before that included several nested if-statements. Vectorizing nested if-statements

As the code I posted there hoping for some ideas I might implement was a bit long and I am still struggeling with the implementation of vectorization for nested loops I would like to ask again with some easier code:

Code

NB_list_all=zeros(length(BML),4);
for NB=1:length(BML);
    NB_list=zeros(4,1);
    %in +x direction
    if isempty(find(BML(:,2)==BML(NB,2)+x_blockdimension & BML(:,3)==BML(NB,3), 1));
        NB_list(1,1)=0;
    else
        NB_list(1,1)=find(BML(:,2)==(BML(NB,2)+x_blockdimension)& BML(:,3)==BML(NB,3));

    end
NB_list_z(NB,:)=NB_list;
end

% BML(:,2) stores the x-coordinate
% BML(:,3) stores the y-coordinate

Some example data

BML=
    1 1005  115
    2 1100  115
    3 1419  120
    4 1424  120
    5 660   115
    6 655   115

Notice BML has a size of 170 000 x 7.

Code Description

What I am trying with this code is finding the next point in my point cloud which is "x_blockdimension" away. If nothing can be found the entry is set to zero. Now as this takes a huge amount of time for 18 Million points (and I am not just looking in one direction) I am looking for a way to optimize this by either using vectorization or logical indexing. If there is another way to improve the runtime I would be happy for any tips.

What I tried

if isempty(find(BML(:,2)==BML(:,2)+x_blockdimension & BML(:,3)==BML(:,3), 1));
    NB_list(1,1)=0;
else
    NB_list(1,1)=find(BML(:,2)==(BML(:,2)+x_blockdimension)& BML(:,3)==BML(:,3));

end

But it is not really doing what I want it to do.

I hope for some help!

Upvotes: 3

Views: 113

Answers (2)

Dave Rayner
Dave Rayner

Reputation: 21

If you know that there is only 0 or 1 match for every row in BML, then you can sort them and use diff, rather than using a loop:

%%  Find matches for x dimension

% sort on x dimension using sortrows, then split the matrix again
BMLx= sortrows(BML(:,[2:end,1]));
sorted_xx = BMLx(:,1:end-1);
idx = BMLx(:,end);

diff_ = diff(sorted_xx);
x_diff_match = find(diff_(:,1)==x_blockdimension & (diff_(:,2:end)==0));
% or you might want to use abs(a-b)<told

% assign all zeros as default
NB_list_x=zeros(length(BML),1);
% alocate matches
NB_list_x(idx(x_diff_match)) = idx(x_diff_match+1)

Upvotes: 1

Divakar
Divakar

Reputation: 221634

If I understood the format of inputs correctly, you can use broadcasting with bsxfun for a vectorized solution like so -

% Perform broadcasted comparison corresponding to the iterative comparison
% in original code to get a boolean array/mask. 
% Get the row, col indices for the mask, which will correspond to the index
% values and positions where those values are to be stored in the output. 
[R,C] = find(bsxfun(@eq,BML(:,2),BML(:,2).'+x_blockdimension) & ...
                                     bsxfun(@eq,BML(:,3),BML(:,3).'));

% Setup output array and store the indices at respcetive positions. 
NB_list_z_out = zeros(size(BML,1),numel(NB_list));
NB_list_z_out(C,1) = R;

Please note that it seemed that the output is only editing the first column elements in the output array and therefore indexing with NB_list_z_out(C,1) at the last step.

An alternative approach could be suggested with focus on memory efficiency and additionally performance too and get R and C, which could be used later on just like they were used in the approach listed earlier. The implementation would look something like this -

% Filter out with "bsxfun(@eq,BML(:,3),BML(:,3).'))".
[~,~,idx] = unique(BML(:,3),'stable');
vidx = find(ismember(idx,find(accumarray(idx(:),1)>1)));

% Filter out on remaining ones with valid indices (vidx)
[R1,C1] = find(bsxfun(@eq,BML(vidx,2),BML(vidx,2).'+x_blockdimension));
R = vidx(R1);
C = vidx(C1);

Upvotes: 1

Related Questions