10
$\begingroup$

I know that Intersection is a pattern matching function and will not evaluate list elements to determine if two or more list have equal elements. So my question is, what can be done to do this? Say, determine if two lists have numerically equal elements within some tolerance dx?

$\endgroup$
  • $\begingroup$ Have you seen the SameTest option? $\endgroup$ – Sjoerd C. de Vries Jul 16 '13 at 22:51
  • $\begingroup$ No, I had not. Thank you. $\endgroup$ – Phillip Dukes Jul 16 '13 at 23:08
  • $\begingroup$ I'm glad you found my answer helpful but you should not be so quick to Accept an answer, as it can discourage other, better, answers from being posted. I suggest you wait 24 hours to let everyone have a chance to answer. $\endgroup$ – Mr.Wizard Jul 16 '13 at 23:21
  • $\begingroup$ I added a method to my answer. Rounding is not ideal as two close values might be rounded in opposite directions but I cannot think of a fast way that obeys a strict tolerance. $\endgroup$ – Mr.Wizard Jul 17 '13 at 6:04
12
$\begingroup$

Closely related questions:


The most direct method is to make use of the SameTest option:

a = {1, 2.2, 3.14159};
b = {11/5, Pi, 1/2, 1/4};

Intersection[a, b, SameTest -> (Abs[# - #2] < 0.0001 &)]
{2.2, 3.14159}

This however requires a pairwise comparison that has a much higher computational complexity than the default method. A different method that does not require a pairwise compare will be much faster on long lists. Iff each list is internally free of duplicates and your tolerance requirement can be relaxed to rounding you could use this:

Cases[GatherBy[Join[b, a], Round[#, 0.0001] &], {x_, _} :> x]
{11/5, π}

Note here that the exact values are returned despite the use of Round, because list b is given first in Join.

The speed advantage can be great:

a = RandomReal[99, 1000];
b = RandomReal[99, 1000];

Intersection[a, b, SameTest -> (Abs[# - #2] < 0.0001 &)]       // Timing // First
Cases[GatherBy[Join[b, a], Round[#, 0.0001] &], {x_, __} :> x] // Timing // First

1.638

0.0011728

If a list is not internally free of duplicates any of those values will be returned as well:

a = {1, 2.2, 3.14159};
b = {11/5, Pi, 1/2, 0.5}; (* note 1/2 and 0.5 *)

Cases[GatherBy[Join[b, a], Round[#, 0.0001] &], {x_, __} :> x]
{11/5, π, 1/2}
$\endgroup$
6
$\begingroup$

Couldn't find a way to do it with built-in functions, but here's a manual loop that's not much slower than Mr.Wizard's solution, but has no problems with duplicates and rounding:

TolerantIntersection[a_List, b_List, dx_] := 
  Module[{sb = Sort@b, i = 1, imax = Length@b, dif},
    Select[Sort@a,
      (While[(dif = sb[[i]] - #) <= -dx, 
         If[i == imax, Return@False]; ++i];
      dif < dx) &]]

P.S. I edited to make the comparisons with dx strict. 'Not much slower' - I mean, in the same order of magnitude, compared to Intersection, actually it's 2-3 times slower. Note, that it's not equivalent to Intersection, in cases like

a = {0.00011, 0.00012};
b = {0.0002};

Intersection returns one arbitrary(?) element from a, my function returns both, which I believe is more correct.

$\endgroup$
  • $\begingroup$ Looks good from here. +1 $\endgroup$ – Mr.Wizard Jul 17 '13 at 8:48
  • $\begingroup$ Hello, can this be generalise to 2D lists, in such a way that it returns the common points of two lists according to a given tolerance (which defines, e.g., the radius of a disk around a given point)? $\endgroup$ – Daniele Binosi Aug 23 '16 at 8:29

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.