Services & Resources / Wolfram Forums / MathGroup Archive
-----

MathGroup Archive 2010

[Date Index] [Thread Index] [Author Index]

Search the Archive

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



  • Prev by Date: Re: Mathematica daily WTF
  • Next by Date: Re: Mathematica daily such and so
  • Previous by thread: Re: newbie list question
  • Next by thread: Re: newbie list question