# fast complement with tolerance between large lists

I want a fast algorithm to get a list of elements to be kicked out of another list. But the kick out criterion is not the exact equivalence, however has a tolerance. Any two elements close enough are considered to be same.

The Complement has SameTest, for example set norm tolerance as 10^-6

e1 = RandomReal[1, {100, 2}];
e2 = e1 + 10^-9;
Complement[e1, e2, SameTest -> (Norm[#1 - #2] < 10^(-6) &) ]


For 100 point set, the timing is still OK, 0.25sec. For 1000, it is already slow, 8sec.

Any better solutions?

• I've tried using SameTest -> SameQ and setting Internal\$SameQTolerance to a higher value, gives a good speed-up, but it's not exactly the same as your SameTest as these are floating point numbers: if 1.1 and 1.0 are the same, 0.1 and 0.2 still may be different. – LLlAMnYP Oct 14 '15 at 8:11

Some data in which some data points are close, others are not, and they're not in corresponding order. (It's not clear whether the lists are supposed to be assumed in the same order, and we're are supposed to compare pairwise in parallel.)

e1 = RandomReal[1, {1000, 2}];
e2 = RandomSample[e1] + RandomReal[{-1.5, 1.5}/10^6, Dimensions[e1]];


OP's way:

r1 = Complement[e1, e2, SameTest -> (Norm[#1 - #2] < 10^(-6) &)]; // AbsoluteTiming
(*  6.41131  *)


Using Nearest and Cases:

nf = Nearest[e2];
r2 = Cases[e1, v_ /; nf[v, {1, 1*^-6}] === {}]; // AbsoluteTiming
(*  0.00242976  *)


Somewhat faster with Pick:

r3 = Pick[e1, Length /@ nf[e1, {1, 1*^-6}], 0]; // AbsoluteTiming
(*  0.00110165  *)


The results can come out in a different order, but they contain the same elements.

Sort@r1 == Sort@r2 == Sort@r3
(*  True  *)

• If you really want save time, nf = Nearest[e2 -> Automatic] is a teensy bit faster.... – Michael E2 Oct 14 '15 at 1:52
• Wow, Thank you so much! Another good example to show how correctly toying with mma built-in function can bring magnitudes of speedup. Sadly, people like me just stuck with damn Complement :( . I like the Pick solution. – matheorem Oct 14 '15 at 6:38