7
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – LLlAMnYP Oct 14 '15 at 8:11
7
$\begingroup$

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  *)
$\endgroup$
  • 1
    $\begingroup$ If you really want save time, nf = Nearest[e2 -> Automatic] is a teensy bit faster.... $\endgroup$ – Michael E2 Oct 14 '15 at 1:52
  • $\begingroup$ 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. $\endgroup$ – matheorem Oct 14 '15 at 6:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.