5
$\begingroup$

I need to find the position of elements in list that are present in close. These are both 2D lists. The code is simple but not as efficient as I want:

 list = RandomReal[{-10, 10}, {50000, 2}];
 close = RandomSample[list, 500];
 Position[list, #] & /@ close // AbsoluteTiming

This takes about 0.76 seconds to complete, Is there a way to make it more efficient? For a better comparison with actual data,list should have 250000 elements and close 50000.

$\endgroup$
4
  • $\begingroup$ Are list and close sorted? What kind of numbers do they contain? $\endgroup$ Aug 9, 2018 at 20:09
  • $\begingroup$ list is about 250000 tuples, {x,y}, where x and y are real numbers. close is about 50000. $\endgroup$ Aug 9, 2018 at 20:12
  • $\begingroup$ Start you question with something like list=RandomReal[{-10, 10}, 15000, WorkingPrecision -> 30]. It would restrict the domain of your question and you will get better tailored answers. $\endgroup$
    – Hector
    Aug 9, 2018 at 20:15
  • $\begingroup$ If close is a subset of list, maybe nF=Nearest[list->"Index"]; nF/@close? $\endgroup$
    – kglr
    Aug 9, 2018 at 20:17

2 Answers 2

6
$\begingroup$

Use Nearest:

list=RandomReal[10, {250000,2}];
close=RandomSample[list, 50000];

nf = Nearest[close->"Index"];
Flatten @ nf[list, {1, 0}]; //AbsoluteTiming

{0.113003, Null}

Update

I think I got it backward, based on your example. Just flip close and list:

list=RandomReal[10, {250000,2}];
close=RandomSample[list, 50000];

nf = Nearest[list->"Index"];
Flatten @ nf[close, {1, 0}]; //RepeatedTiming

{0.052, Null}

$\endgroup$
2
  • $\begingroup$ This is perfect. can you elaborate little bit about why the huge increase in performance? Im assuming because I try to use position on every element of close, but somehow nearest bypasses this? $\endgroup$ Aug 9, 2018 at 20:33
  • 1
    $\begingroup$ @GiovanniBaez Nearest creates a specialized data structure (octree) so that it can quickly find the nearest element. $\endgroup$
    – Carl Woll
    Aug 9, 2018 at 20:42
4
$\begingroup$
SeedRandom[1]
list = RandomReal[1, {25000, 2}];
close =Join [RandomReal[1, {2000, 2}], RandomSample[list, 3000]];
nF = Nearest[list -> "Index"];
res1 = nF @ Intersection[list, close];// RepeatedTiming // First

0.0052

versus

res2 = Position[list, #] & /@ Intersection[list, close] ; // RepeatedTiming // First

2.53

Note: Use Automatic in place of "Index" for versions older than 10+.

$\endgroup$
3
  • $\begingroup$ ... use close in place of Intersection[list, close] if close is a subset of list. $\endgroup$
    – kglr
    Aug 9, 2018 at 20:57
  • $\begingroup$ NearestFunctions are listable, so res1 = nF[Intersection[list, close]]; is a bit faster. $\endgroup$ Aug 10, 2018 at 6:50
  • $\begingroup$ Thank you @Henrik. I will update with your suggestion. $\endgroup$
    – kglr
    Aug 10, 2018 at 6:53

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.