How to increase speed when taking the max from multidimensional array with -inf?

Dear all,

I'm trying to calculate the max from a large multidimensional array where there are a lot of elements with -inf. Because the multidimensional array is large (around 100 million elements), I want matlab to ignore the -inf values when calculating the max. Another problem is the number of -inf can be different in each dimension, so I can't just trim the multidimensional array into a smaller one. Right now I think when I use max, the function is incorporating -inf in the calculation, which makes the computation slower.

To illustrate:

            M=-inf*ones(1,3,1000000);

            M(1,1,1:2)=[1 .5];            
            M(1,2,1:2)=[2 1.5];
            M(1,3,1:2)=[2.3 3];

            tic 
            max(M,[],3)
            toc

            N=ones(1,3,2);
            N(1,1,1:2)=[1 .5];            
            N(1,2,1:2)=[2 1.5];
            N(1,3,1:2)=[2.3 3];
            tic
            max(N,[],3)
            toc

ans =

     1     2     3

Elapsed time is 0.009900 seconds.

ans =

     1     2     3

Elapsed time is 0.004949 seconds.

My matlab version is R2013a. Thank you again for all your time!

Answer 1

[Walter Roberson]

Locating and removing the -inf is going to be slower than leaving them in. Even if you go to mex and use fully optimized code, I am quite certain that bothering to test for -inf and skipping it would be slower than including it.

Leaving them in is not going to affect the result compared to removing them, except in the case where all values along the dimension are -inf, and you have not defined what output you want for that.

If your portion of -inf was much higher still (e.g., 90%+) then my suggestion would be to use sparse arrays to represent the locations that are not -inf. You would still need to be careful, though, as a naive max() on a sparse array would treat the "missing" locations as 0 and 0 might happen to be larger than the actual maximum value. Using sparse arrays would not be efficient for ~50% occupancy.

Answer 2

[James Tursa]

So, your examples are not the same size for one:

            N=ones(1,3,2);  % <-- Not the same size as your inf example

Shouldn't this be:

            N=ones(1,3,1000000);

Also, note that timing of examples like this can be heavily influenced by caching effects etc. For example, you can see a wide difference in timing of the first tic-toc results compared the the last three in this variation of your code:

              M=-inf*ones(1,3,1000000);

              M(1,1,1:2)=[1 .5];            
              M(1,2,1:2)=[2 1.5];
              M(1,3,1:2)=[2.3 3];

              tic 
              max(M,[],3)
              toc

%            N=ones(1,3,2);
            N=ones(1,3,1000000);
            N(1,1,1:2)=[1 .5];            
            N(1,2,1:2)=[2 1.5];
            N(1,3,1:2)=[2.3 3];
            tic
            max(N,[],3)
            toc       

              tic 
              max(M,[],3)
              toc

              tic
              max(N,[],3)
              toc

In fact, simply reversing the order of the M vs N code will change your results, so you would have been wondering how to speed up your code by somehow including -inf's in it!

Bottom line is don't worry about it.

[matlabstarter]

So, your examples are not the same size for one:

N=ones(1,3,2);  % <-- Not the same size as your inf example
Shouldn't this be:
N=ones(1,3,1000000);

Thanks for the response. N=ones(1,3,2); is correct. I was trying to illustrate that max(M,[],3) is incorporating -inf's in the calculation, whereas I just want to take the max, ignoring the -inf. In other words, I want to transform M to N, taking into the account that each dimension may have different number of -inf (not shown in the simple example). Sorry if I didn't articulate clearly in the first post. Thank you.

[James Tursa]

Ah. Got it, now. So you have a huge percentage of -inf that you know(?) will not be needed for the calculation and you were wondering if there was any way to speed up the calculation. Do you know where all of these non-inf spots are, or will you need to find them?

[matlabstarter]

So you have a huge percentage of -inf that you know(?) will not be needed for the calculation and you were wondering if there was any way to speed up the calculation

Yes that's exactly correct! About 50% of the elements in the array is -inf. I don't know where they are but I can find them (which cost more cpu time). One way I tried to solve the problem is to use cell and cellfun, but the solution turns out to be even slower:

              tic
              max(N,[],3)
              toc

              tic

              cellM=cell(1,3); %include this to reflect the additional step needed to calculate
              for i=1:3
                  pos=find(isinf(M(1,i,:))==0);
                  cellM{i}=M(1,i,pos);
              end

              cell2mat(cellfun(@(x) max(x,[],3),cellM,'uni',false))
              toc

I get

ans =

     1     2     3

Elapsed time is 0.005228 seconds.

ans =

     1     2     3

Elapsed time is 0.039841 seconds.

Even when I scale up, it seems that the method using cell was still slower.