7
$\begingroup$

I have a problem, where I generate two lists of points, and I want to see which points are the closest. If I just want to find which ones are exactly the same, I can use Intersection[list1,list2]. I even know that I can use SameTest to define the test. As an example, I could use

testlist1 = Table[k, {k, 0, 25, 0.25}];
testlist2 = Table[k, {k, 0, 49, 0.49}];
Intersection[testlist1, testlist2]

and I get the result

{0., 12.25, 24.5}

I can use SameTest to define a closeness function that will test if the two elements are very close:

testlist1 = Table[k, {k, 0, 25, 0.25}];
testlist2 = Table[k, {k, 0, 49, 0.49}];
Intersection[testlist1, testlist2, 
 SameTest -> (Abs[#1 - #2] <= 0.01 &)]

and now I get the elements

{0., 0.5, 11.75, 12.25, 12.75, 24., 24.5}

For my problem, I have two lists that will always contain at least one pair of corresponding points between the list, although they may not always be equal, and the difference will not always be the same; and there may also be more than one set of corresponding points. I've generated the following code, which (mostly) works, but is slow, and depends on a new function introduced in 10.3 which is labeled as [[EXPERIMENTAL]], specifically, the function DistanceMatrix

testlist1 = Table[k, {k, 0, 25, 0.25}];
testlist2 = Table[k+.0057, {k, 0, 49, 0.49}];
Intersection[testlist1, testlist2, 
 SameTest -> (Abs[#1 - #2] <= Min[DistanceMatrix[testlist1,testlist2]] &)]

which returns

{0.5}

Which is (mostly) correct. See bullet 3 for why I'm unsatisfied with the answer.

Now my problems are these:

  1. This seems inefficient, and runs quite slowly
  2. This depends on an experimental function, which is only available in the latest version of Mathematica (10.3)
  3. This returns the element in the first list called in Intersection corresponding to the SameTest returning true. Rather, I'd like it to return the matching elements from both lists. A dirty solution would be to call Intersection twice, with the lists swapped in the slots, but for a solution that already seems inefficient, I'd rather not call it multiple times.

So: is there a better way to do this? Even returning the current result would be ok, if not ideal. Ideally, a list of pairs would be returned, with each pair corresponding to the matching set.

$\endgroup$
1

3 Answers 3

10
$\begingroup$

DistanceMatrix is fast. It evaluates multiple times in the SameTest. If you rewrite your code, you can see the difference:

min=Min[DistanceMatrix[testlist1,testlist2]];//AbsoluteTiming
{0.000501174,Null}
Intersection[testlist1,testlist2,SameTest->(Abs[#1-#2]<=min&)]//AbsoluteTiming
{0.0236643,{0.5}}

VS original code

Intersection[testlist1,testlist2,SameTest->(Abs[#1-#2]<=Min[DistanceMatrix[testlist1,testlist2]]&)]//AbsoluteTiming
{5.39343,{0.5}}

DistanceMatrix will stay in the future versions of Mathematica. Also you can find DistanceMatrix in HierarchicalClustering package or use this code.

Answering on your 3rd question, you can make it so:

mat=DistanceMatrix[testlist1,testlist2];
pos=Position[mat,Min@mat]
{{3,2}}
testlist1[[pos[[;;,1]]]]
{0.5}
testlist2[[pos[[;;,2]]]]
{0.4957}
$\endgroup$
4
$\begingroup$
mind[l1_List, l2_List] := 
 MinimalBy[Table[{k, First@Nearest[l1, k]}, {k, l2}], Norm]

RepeatedTiming[mind[testlist1, testlist2]]
(* {0.0061, {{0.0057, 0.}}} *)

For huge lists you may change Table for ParallelTable

$\endgroup$
0
$\begingroup$

This is based on the cool solution provided by @rhermans and it simply exploits the NearestFunction instead of Nearest, making his solution almost one order of magnitude faster. So, given the two lists you are working with:

testlist1 = Table[k, {k, 0, 25, 0.25}];
testlist2 = Table[k + .0057, {k, 0, 49, 0.49}];

first define the auxiliary NearestFunction for testlist1 and then define the actual function that computes what you need.

nf1 = Nearest@testlist1
mindFast[l2_List] := MinimalBy[{#, First@nf1@#} & /@ l2, Norm];

Let's compare it with @rhermans 's mind

RepeatedTiming[mind[testlist1, testlist2]]
{0.0048, {{0.0057, 0.}}}

RepeatedTiming[mindFast[testlist2]]
{0.000623, {{0.0057, 0.}}}
$\endgroup$

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.