Using find() is faster than direct logical indexing?
33 views (last 30 days)
Show older comments
Does it make sense that using find() instead of direct logical indexing is faster in this example:
A=randi(100,5e3,5e3);
timeit(@()useFind(A))
timeit(@()useLogical(A))
function B=useFind(A)
I=find(A==2);
B=A;
B(I)=3;
end
function B=useLogical(A)
B=A;
B(A==2)=3;
end
4 Comments
Adam
on 3 Aug 2022
I get similar results, albeit that my PC is about 2½ times slower! Find is typically around 8% slower for me on this example.
Bruno Luong
on 3 Aug 2022
Wonder why I get faster than you guys, my PC is just a normal PC, I don't even have Nvidia card and I'm not a gammer (well if one consider MATLAB is not a game).
Accepted Answer
Jan
on 3 Aug 2022
No relevant difference in R2022a in the forum:
A=randi(100, 5e3, 5e3); % Few elements only
timeit(@() useFind(A))
timeit(@() useLogical(A))
But as soon as the number of occurences grows, the timings differ:
A = randi(2, 5e3, 5e3); % More occurences: about 50%
timeit(@() useFind(A))
timeit(@() useLogical(A))
function B = useFind(A)
I = find(A == 2);
B = A;
B(I) = 3;
end
function B = useLogical(A)
B = A;
B(A == 2) = 3;
end
My interpretation: find has a certain overhead and providing a vector as index is more expensive, because each element must be checked if it is inside the valid range with an integer value. The logical index must be checked only once.
For a tiny index vector, the find method has an advantage, because the logical indexing must process a lot of false elements. This seems to be implemented inefficiently in Matlab, see FEX: CopyMask, which ist much faster (up to 66%!) than Y = X(Mask) with logical indexing. It uses a simple method to avoid branching:
*Y = X[i];
Y += Mask[i];
If the index vector is larger, e.g. 50% of the data, the find() method is less efficient than logical indexing.
6 Comments
Bruno Luong
on 4 Aug 2022
Edited: Bruno Luong
on 4 Aug 2022
But is not Jan's code suppose to do.
It carry out the same task as
Y = X(Mask)
where Mask is a logical array; and Jan claims it's can be twice faster.
There are some variation with working dimension, make Jan's code more flexible.
Jan
on 5 Aug 2022
These two pieces of C code are equivalent:
% iTrue and fTrue are the first and last TRUE elements
% of the logical Mask vector
for (i = iTrue; i <= fTrue; i++) {
*Y = X[i];
Y += Mask[i]; // Advance pointer if Mask is TRUE
}
and
for (i = iTrue; i <= fTrue; i++) {
if (Mask[i]) {
*Y++ = X[i];
}
}
The 1st method avoids branching, which is faster on modern CPUs. If the Mask contains less than about 2.5% TRUE values, the 2nd method is faster.
FEX: CopyMask counts the number of TRUE values at first for a proper pre-allocation. This might be another cause for the speedup compared to X=Y(Mask).
For masking in a specific dimension like Y=X(:, Mask, :), the C-Mex CopyMask is only slightly faster for some specific inputs, but slower usually. So CopyMask is useful for vectors only.
I was really surprised, when I found this simple piece of code to be up to 7 times faster than Matlab's logical indexing.
More Answers (0)
See Also
Categories
Find more on Matrix Indexing in Help Center and File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!