performance of diff on a logical array

I have a 5000x5000 logical array. I want to find the indices where the logical array has a rising edge, e.g. whenever the array goes from 0 to 1 within a row. Until now I did this as follows:

rising_edges = diff(A) == 1;

However, I notice that this is slow. I am pretty certain that this is slow because diff(A) has to allocate new memory for a 5000x5000 double array.

I am wondering: is there a more elegant and faster way of doing this? I'd also be happy with just the subscripts instead of a full logical index array.

Answer 1

[Walter Roberson]

rising_edges = A(:,2:end)) & ~A(:,1:end-1);

this operates on the entire array at the same time. You can use the two-output version of find() on the result, prioritized by row instead of by column. You can put the two outputs together and sortrows() or there are various other ways like findgroups()

[Tom DeLonge]

Thanks Walter. This increases speed 4 fold compared to using diff. It is even a tad faster than using

rising_edges = A(:, 1:end-1) > A(:, 2:end)

I was wondering still why this takes "so long". So I did the following

arr1 = A(:,1:end-1);         % takes 40% of total time
arr2 = A(:,2:end);           % takes 40% of total time
rising_edges = arr1 & ~arr2; % takes 20% of total time

To my surprise, your solution and this 3-line code take (pretty much) the same time. So I suppose what Matlab is doing internally when using your solution: it allocates two arrays and compares those. I wonder if those allocations steps can't be skipped?

In my final function I can use

persistent

to alleviate this to a certain degree. But in general, I wonder if Matlab can't be faster than this. I mean, it's just comparing 25 Million (in my case) binary numbers. The allocation step could in principle be skipped...

[Walter Roberson]

https://www.mathworks.com/matlabcentral/fileexchange/65842-sharedchild-creates-a-shared-data-copy-of-a-contiguous-subsection-of-an-existing-variable

[Tom DeLonge]

oh this is a nice contribution. Indeed, something I've been looking for a while. Let's see whether it is 64-bit compatible...

[Tom DeLonge]

Walter, I checked the contribution. The results are indeed interesting. It turns out, that using sharedchild I get a speedup by a factor of 2. I was quite surprised, I would have expected a 5-fold speedup (as indicated by my stats above). Turns out, that now the actual binary operation takes longer than before (nearly 4 times). The sharedchild-operation however is incredibly fast.

I have no idea what is going on behind the scenes here...

Answer 2

[lokender Rawat]

You can simply declare an array "mat" and do the following, you do not need to create another new double array here. It will find the index from the logical array for each row and put it in "index" variable.

[matRow,matCol]=size(mat)
 for i=1:matRow
     index=find(mat(i,2:end)-mat(i,1:end-1)==1)
 end

[Walter Roberson]

This will overwrite the entire variable index each time through the loop.

[Tom DeLonge]

yes, Robert, thanks for that comment. I was able to increase the speed by a factor of 2 when not using diff, but rather having

A(1:end-1) > A(2:end)

still not really fast, since two logical arrays seem to be allocated here...