File Exchange

image thumbnail

anyEq

version 1.3 (9.37 KB) by

Fast check if 2 arrays have a common element

4 Downloads

Updated

View License

C-Mex: anyEq

This is a simple but fast check, if two arrays contain any common element.
The C-Mex is 25% to 60% faster than the equivalent Matlab expression "any(X(:) == y)" and much faster than "any(ismember(X, Y))" if Y is an array.
If a matching element is found early, this function returns very fast without testing the rest.
In opposite to the Matlab version, the C-mex does not need any temporary arrays.

R = anyEq(X, Y)
INPUT:
X, Y: Arrays of any size. Complex or sparse array are rejected.
Types: DOUBLE, SINGLE, (U)INT8/16/32/64, CHAR, LOGICAL.
OUTPUT:
R: TRUE is replied if any element of X occurs in Y, FALSE otherwise.

NOTES:
- This is equivalent to:
R = any(X(:) == Y(1)) || any(X(:) == Y(2)) || ...
- This MEX version is faster than the Matlab method, because the creation of
the intermediate logical array is avoided:
Worst case (no matching element): 25% to 60% faster
Best case (first element matches): 99.99% faster for 1e6 elements
(Matlab 2011b/64, MSVC 2008).
- For small LOGICAL arrays (< 5'000 elements) anyEq is up to 65% slower than
any(X) or ~all(X). For larger arrays the speedup depends on the position of
the first match and can reach a factor of 7.
- X and Y are ordered automatically such, that the elements of the smaller
array are searched in the larger one.

EXAMPLES:
anyEq(0:0.1:1, 0.3) % FALSE: Effect of limited precision
anyEq(1:4, [5,2]) % TRUE: 2 is found in 1:4

COMPILATION: See anyEq.c for instructions how to compile the C-file.

TEST: Run uTest_anyEq to check validity and speed of the Mex function.

Tested: Matlab 6.5, 7.7, 7.8, 7.13, WinXP/32, Win7/64
Compiler: LCC2.4/3.8, BCC5.5, OWC1.8, MSVC2008/2010

Suggestion and bugreports by email or in the comment section are appreciated.

Comments and Ratings (5)

Brett Shoelson

Brett Shoelson (view profile)

Hi Jan...just wondering how this compares to

~isempty(intersect(X,Y))

Regards,
Brett

Jan Simon

Jan Simon (view profile)

@William: Thanks for your comments.
I've added a support for logical input now. While anyEq(X,Y) is 25% to 50% faster than ANY(X==Y) for numerical arrays, for LOGICAL input it depends on the application, if this is faster or slower than ANY(X) or ~ALL(X):
x = false(1, 1e6); anyEq(x, true); is 7 times faster than any(x). But anyEq(x, false) needs 65% more processing time than ~all(x). Fortunately the absolute time difference is small even then.

Extremely rapid short-circuiting "any" checking. I am using this to compare large logical 3D arrays, and despite your own comments in the file documentation, it is actually even faster than the built-in any on my data. It is unfortunate this doesn't support logical inputs, because then I have to use find on my logical arrays first, and I could probably see some small speed improvement comparing logical arrays directly.

And yes, it is still faster than the built-in any even with two find calls on equally sized arrays. According to the profiler, its about twice as fast.

Jan Simon

Jan Simon (view profile)

For running the unit-test in Matlab 6.5 a replacement for the newer "cast" function is required:
function y = cast(x, t)
y = feval(t, x)

Updates

1.3

Accepts LOGICALs also.

1.2

Tested under 64 bit.

MATLAB Release
MATLAB 7.13 (R2011b)

Download apps, toolboxes, and other File Exchange content using Add-On Explorer in MATLAB.

» Watch video