Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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?

share|improve this question
3  
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
1  
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
1  
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
1  
And don't forget to accept any answers that work for you... –  cormullion Mar 22 '13 at 8:30
show 6 more comments

5 Answers

up vote 7 down vote accepted

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}
share|improve this answer
    
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
add comment

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

share|improve this answer
    
I have a bigList,each sublist is different.so in my case union is not usefull. –  subbu Mar 22 '13 at 11:04
add comment
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.

share|improve this answer
    
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
1  
@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
1  
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
2  
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
add comment

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.

share|improve this answer
    
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
add comment

Prompted by comments conversation with Mr. Wizard, a routine I use:

findMultiPosXX[list_, find_, allowBits_: False, skipCands_: True] := 
 Module[{f = DeleteDuplicates[find], o, l, oo, bitmax = 20, cands, dims},

  If[allowBits && Length@f <= bitmax,
   With[{r = If[Length@(dims = Dimensions@list) == 1, Range@Length@list, 
                Array[List, dims]]}, Pick[r, BitXor[list, #], 0] & /@ f],

   If[skipCands,

    (l = Length@f;
     oo = Ordering[o = Ordering[Join[f, list, f]]]; 
     Inner[o[[# ;; #2]] &, oo[[;; l]], oo[[-l ;;]], List][[All, 2 ;; -2]] - l),

    (cands = 
      SparseArray[
        BitAnd[UnitStep[list - Min@f], UnitStep[Max@f - list]]]["NonzeroPositions"];

     cands[[#]] & /@ (l = Length@f;
       oo = Ordering[o = Ordering[Join[f, Extract[list, cands], f]]]; 
       Inner[o[[# ;; #2]] &, oo[[;; l]], oo[[-l ;;]], List][[All, 2 ;; -2]] - l))]]];

Use:

test = RandomInteger[10, 20]

findMultiPosXX[test, {5, 10, 8}]

(*

{10, 0, 1, 4, 10, 5, 7, 2, 7, 7, 1, 4, 9, 3, 3, 7, 7, 8, 2, 5}

{{6, 20}, {1, 5}, {18}}

*)

With default argument (just the target and searches), can beat GatherBy by order of magnitude, and Position with Alternatives (which leaves you with only positions but no mapping to values) by a factor of 5 or more.

When searching for scalar values at the top level, setting the third argument to True will use bit-map search for 20 or fewer search terms, upping the performance typically by 4-10X. Also for scalar searches, if one knows the search space spans a small range of the data range, setting the fourth argument to False causes the search space to be narrowed, boosting performance from 2X to over an order of magnitude.

E.g., testing against several of the answers and Position with Alternatives, using the OP specified sizes with test = RandomInteger[1000000, {60000, 3}] and finds = RandomSample[test, 1200], the speed advantage results expressed as time/mytime were {7.4286, 6.1429, 20.857, 21.143, 419.71}.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.