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$
  • $\begingroup$ Are list and close sorted? What kind of numbers do they contain? $\endgroup$ – Marius Ladegård Meyer Aug 9 '18 at 20:09
  • $\begingroup$ list is about 250000 tuples, {x,y}, where x and y are real numbers. close is about 50000. $\endgroup$ – Giovanni Baez Aug 9 '18 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 '18 at 20:15
  • $\begingroup$ If close is a subset of list, maybe nF=Nearest[list->"Index"]; nF/@close? $\endgroup$ – kglr Aug 9 '18 at 20:17
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$
  • $\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$ – Giovanni Baez Aug 9 '18 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 '18 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$
  • $\begingroup$ ... use close in place of Intersection[list, close] if close is a subset of list. $\endgroup$ – kglr Aug 9 '18 at 20:57
  • $\begingroup$ NearestFunctions are listable, so res1 = nF[Intersection[list, close]]; is a bit faster. $\endgroup$ – Henrik Schumacher Aug 10 '18 at 6:50
  • $\begingroup$ Thank you @Henrik. I will update with your suggestion. $\endgroup$ – kglr Aug 10 '18 at 6:53

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.