8
$\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?

Improve this question
$\endgroup$
1
  • $\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
    Commented Oct 14, 2015 at 8:11

1 Answer 1

Reset to default
9
$\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  *)
Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ If you really want save time, nf = Nearest[e2 -> Automatic] is a teensy bit faster.... $\endgroup$
    – Michael E2
    Commented Oct 14, 2015 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
    Commented Oct 14, 2015 at 6:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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