Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

To resolve issues starting MATLAB on Mac OS X 10.10 (Yosemite) visit: http://www.mathworks.com/matlabcentral/answers/159016

speed up finding common values in multiple matrices

Asked by Alexander on 23 Sep 2011

I have three same-sized matrices (approx. 2000x2000). I am iteratively evaluating these matrices thousands of times and desperately need to speed up the processing. Here's what I'm trying to do:

A is a logical matrix

B contains integer values

C is a logical matrix

For a given value z, I need to find where B==z and A==1, and change these locations in C to ones, or:

C(B==z & A == 1) = 1;

Any ideas on speeding up would be fantastic. I'm not seeing how. Many thanks in advance.

1 Comment

Fangjun Jiang on 23 Sep 2011

Do you mean you currently use C(B==z & A == 1) = 1; and it's not fast enough?

Alexander

3 Answers

Answer by Walter Roberson on 23 Sep 2011
Accepted answer

How "dense" is A? If there are relatively few locations set in A compared to the size of A, then

locs = find(A);
C(locs(B(locs)==z)) = true;

Note that if A is not changing, then you only need to compute locs once before you start the iterations.

3 Comments

Alexander on 23 Sep 2011

A is pretty dense, about half the elements are ones. Plus it is A that is changing across iterations. Thanks for the suggestion though.

Walter Roberson on 23 Sep 2011

Darn, so much for that idea.

Okay... there is a possibility that this would be faster than what you have (but I suspect not):

C = (B == Z & A == 1) | C;

Ah, and of course I should have asked about the density of B==Z, as the find() can be switched around:

locs = find(B==z);
C(locs(A(locs))) = true;

Alexander on 24 Sep 2011

Yes, going the find(B==z) route sped this up quite a bit, about a 30% improvement over my original code. Good suggestion.

Walter Roberson
Answer by Fangjun Jiang on 23 Sep 2011

If A is a logical matrix, A==1 is not needed. If C is a logical matrix, use true/false at the right hand side.

C(B==z & A) = true;

I wonder if this will help.

4 Comments

Fangjun Jiang on 23 Sep 2011

Well, on my computer using R2007b. It's more than 2 times faster.
%%
N=2000;
A=false(N);
A(1:2:N*N)=true;

B=magic(N);
C=false(N);

z=100;
t1=0;
t2=0;
for k=1:100
tic;
C(B==z & A == 1) = 1;
t1=t1+toc;

tic;
C(B==z & A) = true;
t2=t2+toc;
end

fprintf('t1=%f\n',t1);
fprintf('t2=%f\n',t2);

t1=8.257074
t2=3.571116

Fangjun Jiang on 23 Sep 2011

And I switched the order of approach 1 and 2 inside the for-loop, the result is the same.

Alexander on 24 Sep 2011

Yes, you are correct. In my code, A had turned into a double. Once A became a logical like it is supposed to, your suggestion improved the speed about 20% on my computer. Walter's suggestion is a bit faster though...since B is relatively sparse, the find(B==z) doesn;t cost much so the below is about 10% faster than your suggestion. Thanks.

locs = find(B==z);
C(locs(A(locs))) = true;

Fangjun Jiang
Answer by Derek O'Connor on 24 Sep 2011

Here are some tests on loopy alternatives to vectorized functions.

    %-----------------------------------
     function [z,A,B,C] = GenDat(m,n)
    %
    % Derek O'Connor 24 Sep 2011
    %
    B = ceil(m*n*rand(m,n));    % B is integer
    A = round(rand(m,n)) == 1;  % A & C are logical
    C = A;
    z = m*n*rand;
    % --------  end GenDat ---------
    %-------------------------------------------------------
      function C = UpDate0(z,A,B)
    [m,n] = size(A);
    C(1:m,1:n) = false;
    C(B==z & A == 1) = true; % = 1 slows this operation
    %
    %-----------------------------------------
     function C = UpDateDOC1(z,A,B)
    [m,n] = size(A);
    A = A(:);
    C(1:m,1:n) = false;
    for i = 1:m
        for j = 1:n
            if B(i,j) == z
                if A(i,j)
                    C(i,j) = true;
                end
            end % endif B
        end % endfor j
    end % endfor i
    %-----------------------------------------
     function C = UpdateDOC2(z,A,B)
    [m,n] = size(A);
    C(1:m,1:n) = false;
    A = A(:);
    B = B(:);
    C = C(:);
    for k = 1:m*n
        if B(k) == z
            if A(k)
                C(k) = true;
            end
        end % endif B
    end % endfor k
    %-----------------------------------------  
     function C = UpdateWal1(z,A,B)
    % Walter Roberson's function.
    %
     locs = find(A);
     C(locs(B(locs)==z)) = true;
    %-----------------------------------------  
     function C = UpDateWal2(z,A,B)
     locs = find(B==z); 
     C(locs(A(locs))) = true;
%---------------------------------------------------------     

Timing tests for n = [500 1000 2000 3000], run 10 times gave these normalized average times

                            Normalized Average Times
               n    UpDate0   UpDateDOC1   UpDateDOC2  UpDateWal1
             -------------------------------------------------------
              500    1.17       1            1.03        1.94
             1000    1.15       1.14         1           2.35
             2000    1.09       1.14         1           2.23
             3000    1.14       1.14         1           2.32
             -------------------------------------------------------    
 Actual(secs)3000    0.16       0.17         0.14        0.33
                    R2008a 64-bit, Windows 7, 2.33GHz

These results are for random A,B,z but I suspect these times will depend very much on the actual inputs.

As you can see, not much of a speed-up. Given that the matrices are dense and there is no pattern to the updates, it's hard for me to see how this operation can be speeded up.

Perhaps if you accumulated a vector of z values and did a single update for the vector then this should give a speed-up. But "batching" the z values may not be possible.

UPDATE 1

I overlooked Walter's second method, which is remarkably fast

                                 Normalized Average Times                 
                n   UpDate0  UpDateDOC1 UpDateDOC2  UpDateWal1  UpDateWal2
              ------------------------------------------------------------
               500   4.27       3.64       3.81       6.86           1    
              1000   3.31       3.16       2.71       7.09           1    
              2000   3.39       3.42       2.96       7.00           1    
              3000   3.34       3.43       2.87       6.83           1    
              ------------------------------------------------------------
 Actual(secs) 3000   0.17       0.17       0.14       0.34          0.05

This shows that vectorization can give great speed-ups, if you choose the right one.

UPDATE 2

This table shows the dramatic effect the JIT accelerator has on loopy functions

                 Times(Acc off)/Times(Acc on)
          n       UD0     DOC1   DOC2     Wal1  Wal2
        --------------------------------------------
         500      1.3     45.4   38.6     1.2   1.0
        1000      1.6     41.1   40.5     1.0   1.1
        2000      1.6     39.2   39.4     1.0   1.1
        3000      1.6     38.4   38.9     1.0   1.0
        --------------------------------------------
            R2008a 64-bit, Windows 7, 2.33GHz

3 Comments

Walter Roberson on 24 Sep 2011

Yah Team Roberson!

Derek O'Connor on 25 Sep 2011

Walter,

It would be useful if you would explain why your two methods have a 7:1 speed ratio. Both use Matlab's find() function, so perhaps a brief explanation of how it works in this would be helpful also.

Walter Roberson on 25 Sep 2011

In theory, it depends entirely on the density of matches. The lower the number of matches, the smaller the result of find() and the fewer locations that need to be checked for the following comparison.

In practice, for the same density, one would expect the first variant, checking logical matrix (A) first, would be faster, as one would expect the comparison step followed by logical indexing by the result of the comparison, to be slower than plain logical indexing. Of course, expectations should be put to the timing test...

Derek O'Connor

Contact us