# Efficiently finding the positions of a large list of targets in another, even larger list

I have a big list. It contains nearly 60,000 sub-lists. It's structured like

  bigList= {{x1,y1,z1},{x2,y2,z2},{x3,y3,z3},.....,{x60000,y60000,z60000}};


Randomly, I have picked 1200 elements from the bigList.

  smallList={{x1,y1,z1},{x2,y2,z2},......,{x1200,y1200,z1200}};


I want to find the positions of the smallList elements from the bigList. To that end I wrote the following code.

   Flatten[Map[Position[bigList, #]&, smallList] ]


It's working fine, but it takes 30 seconds to evaluate.

 Timing[Flatten[Map[Position[bigList, #]&, smallList] ]]


How can I reduce that evaluation time?

-
Since you know the number of elements in your list (60k) and its sublist structure (3 elements), why don't you just pick the positions at random from a list of possible positions, instead of picking the elements and then using Position (which is very slow)? It's the same and should be very fast. Even if you need to construct smallList, you can use these randomly generated positions and extract the elements using Part, which would still be faster. Also, your pure function construction in Map is incorrect... –  rm -rf Mar 22 '13 at 6:21
@rm-rf I can imagine that he is just describing how to get test data, but the question is phrased rather ambiguous indeed. –  Sjoerd C. de Vries Mar 22 '13 at 6:45
I think the problem should be rephrased as something like : With bigList = RandomInteger[{1, 255}, {60000, 3}]; smallList = RandomChoice[bigList, 1200]; try to decrease : First[Timing[Flatten[Map[Position[bigList, #] &, smallList]]]]. If the OP confirms this is what he wants, I can do it myself. –  andre Mar 22 '13 at 8:06
Are all sublists unique or do you want to find all occurences of a given sublist? –  Sjoerd C. de Vries Mar 22 '13 at 8:18
And don't forget to accept any answers that work for you... –  cormullion Mar 22 '13 at 8:30

I will use big and small rather than bigList and smallList, for brevity.

As stated by others if you can select the positions at random in the first place this will be faster, e.g.:

pos = RandomSample[Range @ Length @ big, 1200];


You can then get the small list with: small = big[[pos]].

To carry out the specific operation you describe the key detail will be to not scan the big list again for every element of small but rather find a way to scan it only once.

One of the simplest methods is to use MapIndexed to build a list of replacement rules that yield positions from elements. MapIndexed is easily extendable to array and tensor elements as well. Dispatch can be used to optimize this list of replacement rules.

Example data:

big = Array[{"x", "y", "z"} # &, 60000];

small = RandomSample[big, 1200];


Build the dispatch table:

rls = MapIndexed[Rule, big] // Dispatch;


Find the positions:

pos = small /. rls;


Together both operations take less than a tenth of a second on my machine:

First @ Timing[small /. Dispatch @ MapIndexed[Rule, big];]


0.0966

Confirmation of accuracy:

Extract[big, pos] === small


True

### Lists with duplicates

The method above assumes that your big list does not have any duplicate elements; that is, there is a one-to-one mapping of element and position. If there are duplicates you will need an additional GatherBy step as follows.

Data with duplicates:

big = Array[{"x", "y", "z"} Mod[#, 5000] &, 60000];
small = RandomSample[big, 1200];


Build rules, Gather them, and build the Dispatch table:

rls2 =
Dispatch[
#[[1, 1]] -> #[[All, 2, 1]] & /@
Rule ~MapIndexed~ big ~GatherBy~ First
];


Find the positions in big at which the first element of small appears:

First @ small /. rls2

{2659, 7659, 12659, 17659, 22659, 27659, 32659, 37659, 42659, 47659, 52659, 57659}


Instead of GatherBy you could also use Sow and Reap, e.g.:

rls2 = Dispatch @ Reap[MapIndexed[Sow[#2, #] &, big], _, # -> Flatten@#2 &][[2]];


### Alternative method

To provide an alternative approach you can use DownValues definitions in place of the Dispatch table. I shall illustrate the method for a list with duplicates as that is more interesting.

Data:

SeedRandom[1]
big = RandomInteger[9, 50];
small = {6, 3, 9, 7, 2};


Build the definitions:

Clear[posfn]

posfn[_] = {};

AppendTo[posfn[#], #2[[1]]] & ~MapIndexed~ big;


Test the function:

posfn /@ small

{{8, 20, 23}, {17, 27, 30, 32, 34, 36, 42}, {37, 43}, {4}, {18, 22, 35, 41, 50}}


Confirmation:

big[[ posfn[3] ]]

{3, 3, 3, 3, 3, 3, 3}

-
Thank you.really it's awesome.working fine.really you done good job...Really thanks Wizard.Thanks,Thanks,Thanks –  subbu Mar 22 '13 at 14:22
@subbu You're welcome. You see that I am not unwilling to help, I just want you to put some effort into reading and understanding the Mathematica documentation. If you do not you will end up with "cargo cult programming." –  Mr.Wizard Mar 22 '13 at 14:33
bigList = RandomSample[DeleteDuplicates[RandomInteger[{1, 255}, {70000, 3}]], 60000];
smallList = RandomSample[bigList, 1200];
First@AbsoluteTiming[Map[Position[bigList, #] &, smallList]]


needs less than a second on my machine.

-
Really I didn't understood.specifically you are not use any function.but computation takes only less than a second.just for example purpose we are using RandomIntegers,I have 60000point,each point is different.know How can I implement your logic in my code. can you tell me ? –  subbu Mar 22 '13 at 11:18
@subbu: just read the documentations of RandomSample, etc. Then you will understand. And please, take some time for it. Learning takes time. Really. You need about 5 years to master Mathematica. A PhD also helps. –  Rolf Mertig Mar 22 '13 at 11:21
I think subbu means: your code is the same as his (apart from Flatten), so how can it be that much faster? –  Sjoerd C. de Vries Mar 22 '13 at 13:03
The difference lies in the uniqueness of the values of bigList. If it has duplicates, running time of the code goes through the roof. –  Sjoerd C. de Vries Mar 22 '13 at 13:27

An approach like @Rolf-Merting's using a nearest function. First create the lists:

bigList = RandomSample[DeleteDuplicates[RandomInteger[{1, 255}, {70000, 3}]], 60000];
smallList = RandomSample[bigList, 1200];


then create a nearest function mapping to list indices:

nf = Nearest[Thread[bigList -> Range@Length@bigList]];


then map nf to the small list and get back the positions:

AbsoluteTiming[nf /@ smallList;]


overall (together with the creation of the nearest function) it is slightly faster.

-
This is a fine solution that even works (i.e., is speedy) if bigList has duplicates which seems to be subbu's problem. One has to guarantee that smallList is sampled from bigList, but that seems to be a given here. –  Sjoerd C. de Vries Mar 22 '13 at 13:52
@Sjoerd At least with version 7 this does not work on my non-numeric test set. How about in v9? –  Mr.Wizard Mar 22 '13 at 14:34
This wouldn't work on symbolic ones - I didn't realise that was part of the question. One could convert them to strings and then find the nearest function but I that would take forever I think. –  gpap Mar 22 '13 at 14:50
@Mr.Wizard I suppose it will work for lists with elements on which a distance function yields a definite value. Your demo list is probably not what the OP is working with, he only provided the list symbolically to show the structure. –  Sjoerd C. de Vries Mar 22 '13 at 14:57

I wonder whether this helps. Union removes duplicates and sorts:

bigList = Union@RandomInteger[{1, 255}, {60000, 3}];
smallList = RandomChoice[bigList, 1200];
First@AbsoluteTiming[ Map[Position[bigList, #] &, smallList]]


and it's therefore much quicker.

0.833301

-
I have a bigList,each sublist is different.so in my case union is not usefull. –  subbu Mar 22 '13 at 11:04