Skip to content

Instantly share code, notes, and snippets.

@amroamroamro
Created April 10, 2015 18:01
Show Gist options
  • Save amroamroamro/e66ac6a88b0692d995fd to your computer and use it in GitHub Desktop.
Save amroamroamro/e66ac6a88b0692d995fd to your computer and use it in GitHub Desktop.
[MATLAB] Comparison of array searching implementations

Comparison of different array searching implementation in MATLAB

http://stackoverflow.com/a/1913831/97160

Two benchmarks are included, one for searching a single value, another for searching multiple values (vectorized version).

You could also try different matrix sizes, as well as changing the search values (compare best case where all values are found in the array vs. worst case scenario when none of the values are found).

Note: Floating-point comparison is not considered here! See ismembertol function for that.

function [t,v] = testInArray()
% MATLAB: 8.5.0.197613 (R2015a)
% searching
A = randi(1000, [500 600]); % haystack
x = 10; % needle
% compare implementations
f = {
@() func_eq(A,x);
@() func_eq_earlyexit(A,x);
@() func_ismember(A,x)
};
% time and check results
t = cellfun(@timeit, f, 'UniformOutput',true);
v = cellfun(@feval, f, 'UniformOutput',true);
assert(all(diff(v)==0));
end
function v = func_eq(A,x)
% compare all elements of A against x
v = any(A(:) == x);
end
function v = func_eq_earlyexit(A,x)
% loop (with early-exit)
v = false;
for i=1:numel(A)
if A(i) == x
v = true;
return;
end
end
end
function v = func_ismember(A,x)
% ISMEMBER
v = ismember(x,A);
end
function [t,v] = testInArray_Vectorized()
% MATLAB: 8.5.0.197613 (R2015a)
% searching
A = randi(1000, [500 600]); % haystack
x = [10,40,20,30]; % needle
% compare implementations
f = {
@() func_eq_loop(A,x);
@() func_eq_arrayfun(A,x);
@() func_eq_bsxfun(A,x);
@() func_eq_earlyexit(A,x);
@() func_ismember(A,x)
};
% time and check results
t = cellfun(@timeit, f, 'UniformOutput',true);
v = cellfun(@feval, f, 'UniformOutput',false);
assert(isequal(v{:}));
end
function v = func_eq_loop(A,x)
% compare all elements of A against every value in x
v = false(size(x));
for j=1:numel(x)
v(j) = any(A(:) == x(j));
end
end
function v = func_eq_arrayfun(A,x)
% use ARRAYFUN instead of an explicit loop
v = arrayfun(@(xx) any(A(:) == xx), x);
end
function v = func_eq_bsxfun(A,x)
% vectorized BSXFUN call
% (the downside is that it creates a large intermediate matrix)
%assert(isrow(x))
v = any(bsxfun(@eq, A(:), x), 1);
end
function v = func_eq_earlyexit(A,x)
% nested loops (with early-exit)
v = false(size(x));
for j=1:numel(x)
for i=1:numel(A)
if A(i) == x(j)
v(j) = true;
break;
end
end
end
end
function v = func_ismember(A,x)
% ISMEMBER
v = ismember(x,A);
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment