CODEWITHSUNDEEP
performancematlaboptimization
Eleonora Ciceri
Eleonora Ciceri

Reputation: 1798

Fast check if element is in MATLAB matrix

I would like to verify whether an element is present in a MATLAB matrix.

At the beginning, I implemented as follows:

if ~isempty(find(matrix(:) == element))

which is obviously slow. Thus, I changed to:

if sum(matrix(:) == element) ~= 0

but this is again slow: I am calling a lot of times the function that contains this instruction, and I lose 14 seconds each time!

Is there a way of further optimize this instruction?

Thanks.

Upvotes: 2

Views: 626

Answers (2)

horchler
horchler

Reputation: 18504

If you just need to know if a value exists in a matrix, using the second argument of find to specify that you just want one value will be slightly faster (25-50%) and even a bit faster than using sum, at least on my machine. An example:

matrix = randi(100,1e4,1e4);
element = 50;
~isempty(find(matrix(:)==element,1))

However, in recent versions of Matlab (I'm using R2014b), nnz is finally faster for this operation, so:

matrix = randi(100,1e4,1e4);
element = 50;
nnz(matrix==element)~=0

On my machine this is about 2.8 times faster than any other approach (including using any, strangely) for the example provided. To my mind, this solution also has the benefit of being the most readable.

Upvotes: 5

Adrien
Adrien

Reputation: 1475

In my opinion, there are several things you could try to improve performance:

  1. following your initial idea, i would go for the function any to test is any of the equality tests had a success:

    if any(matrix(:) == element)

I tested this on a 1000 by 1000 matrix and it is faster than the solutions you have tested.

  1. I do not think that the unfolding matrix(:) is penalizing since it is equivalent to a reshape and Matlab does this in a smart way where it does not actually allocate and move memory since you are not modifying the temporary object matrix(:)

  2. If your does not change between the calls to the function or changes rarely you could simply use another vector containing all the elements of your matrix, but sorted. This way you could use a more efficient search algorithm O(log(N)) test for the presence of your element.

  3. I personally like the ismember function for this kind of problems. It might not be the fastest but for non critical parts of the code it greatly improves readability and code maintenance (and I prefer to spend one hour coding something that will take day to run than spending one day to code something that will run in one hour (this of course depends on how often you use this program, but it is something one should never forget)

  4. If you can have a sorted copy of the elements of your matrix, you could consider using the undocumented Matlab function ismembc but remember that inputs must be sorted non-sparse non-NaN values.

  5. If performance really is critical you might want to write your own mex file and for this task you could even include some simple parallelization using openmp.

Hope this helps,

Adrien.

Upvotes: 4

Related Questions