Re: newbie list question
- To: mathgroup at smc.vnet.net
- Subject: [mg115027] Re: newbie list question
- From: Daniel Lichtblau <danl at wolfram.com>
- Date: Tue, 28 Dec 2010 06:53:32 -0500 (EST)
----- Original Message -----
> From: "Gareth Edwards" <gareth.edwards at cubicmotion.com>
> To: mathgroup at smc.vnet.net
> Sent: Sunday, December 26, 2010 3:02:23 AM
> Subject: [mg114986] newbie list question
> Hi,
>
> Liking Mathematica a lot, but struggling with the early part of the
> learning curve, i.e. don't know what I don't know...
>
> What would be the neatest syntax for finding the first location of
> elements from one list in another? For example:
>
> listA = { 4,5,8,2,6,4 }
> listB = { 8,4,2 }
>
>
> I would like a function to return {3,1,4} in this case (the first
> location in A of each element in B)
>
> Many thanks!
Neatest is subject to debate. A straightforward and simple method is to Map Position (of element in first list) over the second list.
firstPositions1[l1_, l2_] := Flatten[Map[Position[l1, #, 1, 1] &, l2]]
This will be fine provided the second list is not too large; it scales as m1*m2 where mj is the length of list j. A method that is slower per element of list2, but scales as O(m1+m2), is shown below.
firstPositions2[l1_, l2_] := Module[
{stor, elem, tab},
tab = ConstantArray[0, Length[l2]];
MapIndexed[If[! IntegerQ[stor[#1]], stor[#1] = #2[[1]]] &, l2];
Do[
elem = stor[l1[[j]]];
If[IntegerQ[elem],
stor[l1[[j]]] = False;
tab[[elem]] = j;
], {j, Length[l1]}];
tab]
Quick test that these work.
listA = {4, 5, 8, 2, 6, 4};
listB = {8, 4, 2};
In[85]:= firstPositions1[listA, listB] ==
firstPositions2[listA, listB] ==
IntegerDigits[IntegerPart[100*Pi]]
Out[85]= True
If the second list has 10 or so elements, the second method is noticeably slower than the first. But it does in fact scale much better. Here we compare speed when second list is 1000 elements (not necessarily unique).
l1 = RandomInteger[10^6, 5*10^5];
l2 = RandomInteger[10^6, 10^3];
In[73]:= Timing[pos1 = firstPositions1[l1, l2];]
Out[73]= {68.11000000000001, Null}
In[74]:= Timing[pos2 = firstPositions2[l1, l2];]
Out[74]= {1.933999999999969, Null}
Notice there is a difference in behavior beyond speed. If the second list contains values not found in the first, the second result will have zeros in those corresponding slots. I'm guessing this is probably desirable behavior, as compared to omitting them altogether (since you won't otherwise know what element in result corresponds to what element in second list).
In[75]:= pos1 == DeleteCases[pos2, 0]
Out[75]= True
In[76]:= Length[pos1]
Out[76]= 379
Daniel Lichtblau
Wolfram Research