Perfomance in Position

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.

• Are list and close sorted? What kind of numbers do they contain? – Marius Ladegård Meyer Aug 9 '18 at 20:09
• list is about 250000 tuples, {x,y}, where x and y are real numbers. close is about 50000. – Giovanni Baez Aug 9 '18 at 20:12
• 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. – Hector Aug 9 '18 at 20:15
• If close is a subset of list, maybe nF=Nearest[list->"Index"]; nF/@close? – kglr Aug 9 '18 at 20:17

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}

• 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? – Giovanni Baez Aug 9 '18 at 20:33
• @GiovanniBaez Nearest creates a specialized data structure (octree) so that it can quickly find the nearest element. – Carl Woll Aug 9 '18 at 20:42
SeedRandom
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+.

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