performance of diff on a logical array

2018 2 27
2 个回答
回答已采纳
更新时间：2018 3 9
3 次查看（30 天）

0 个投票

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.

请先登录，再回答此问题。

 采纳的回答

Walter Roberson
Walter Roberson 2018-3-9

0 个投票

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()

4 个评论
显示 2更早的评论 隐藏 2更早的评论

Tom DeLonge
Tom DeLonge 2018-3-9
编辑：Tom DeLonge 2018-3-9
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...
Tom DeLonge
Tom DeLonge 2018-3-9
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
Tom DeLonge 2018-3-9
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...

请先登录，再进行评论。

更多回答（1 个）

lokender Rawat
lokender Rawat 2018-3-9

0 个投票

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

2 个评论
显示 无 隐藏 无

Walter Roberson
Walter Roberson 2018-3-9
This will overwrite the entire variable index each time through the loop.
Tom DeLonge
Tom DeLonge 2018-3-9
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...

请先登录，再进行评论。

类别

在 帮助中心 和 File Exchange 中查找有关 Matrix Indexing 的更多信息

标签

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by