Re: Re: Re: finding the position of a pattern in list (Correction)

*To*: mathgroup at smc.vnet.net*Subject*: [mg64660] Re: [mg64619] Re: Re: [mg64583] finding the position of a pattern in list (Correction)*From*: "Carl K. Woll" <carlw at wolfram.com>*Date*: Sat, 25 Feb 2006 02:53:21 -0500 (EST)*References*: <200602240518.AAA17528@smc.vnet.net> <C187B55A-4417-481E-A6E7-394BCE24F6E5@mimuw.edu.pl>*Sender*: owner-wri-mathgroup at wolfram.com

Andrzej Kozlowski wrote: > It is possible to do it still much faster by applying the method > advocated a number of times on this list by Carl Woll (who seems to > have finally grown tired of doing so I am posting this instead ;-)) > > Here is the Woll approach: > > pos4[l_] := SparseArray[ > Sign[ListConvolve[{-1, > 1}, l] + 1] - 1] /. SparseArray[_, _, _, p_] :> Flatten[p[[2, 2]]] > > Let's compare it with pos3 below: > > pos3[data_] := Position[Most[RotateLeft[data]] - Most[data], 1] // > Flatten; > > > In[3]:= > data = Table[Random[Integer], {10^5}]; > > In[4]:= > Timing[a = pos4[data]; ] > > Out[4]= > {0.04354899999999995*Second, Null} > > In[5]:= > Timing[b = pos3[data]; ] > > Out[5]= > {0.12303199999999992*Second, Null} > > In[6]:= > a == b > > Out[6]= > True > Andrzej, Thanks for advocating my "method" while I've been attending another matter. There's been a new addition to my family, and I've been enjoying that. Concerning your implementation, I would construct the sparse array differently, avoiding ListConvolve: pos5[li_] := Module[{m, r}, m = Most[li]; r = Rest[li]; SparseArray[(r - m)r] /. SparseArray[_,_,_,p_]:>Flatten[p[[2,2]]] ] Comparing: d = Table[Random[Integer], {10^6}]; In[22]:= r1=pos4[d];//Timing r2=pos5[d];//Timing r1===r2 Out[22]= {0.266 Second,Null} Out[23]= {0.109 Second,Null} Out[24]= True Carl Woll Wolfram Research > > Andrzej Kozlowski > > On 24 Feb 2006, at 06:18, Bob Hanlon wrote: > >> There is an error in my second method. It will indicate a match for >> the last >> position if the first data element is 1 and the last data element is >> 0. For >> example, >> >> pos1[data_]:=Position[Partition[data,2,1],{0,1}]//Flatten; >> >> pos2[data_]:=Position[RotateLeft[data]-data,1]//Flatten; >> >> data={1,0,0,1,0,0,1,0}; >> >> pos1[data] >> >> {3,6} >> >> pos2[data] >> >> {3,6,8} >> >> The correct method is >> >> pos3[data_]:=Position[Most[RotateLeft[data]]-Most[data],1]//Flatten; >> >> pos3[data] >> >> {3,6} >> >> The revision is still much faster than the original. >> >> data=Table[Random[Integer],{100000}]; >> >> pos1[data]==pos3[data] >> >> True >> >> Timing[pos1[data]][[1]] >> >> 0.389007 Second >> >> Timing[pos3[data]][[1]] >> >> 0.132175 Second >> >> >> Bob Hanlon >> >>> >>> From: Bob Hanlon <hanlonr at cox.net> To: mathgroup at smc.vnet.net >> >>> Subject: [mg64660] [mg64619] Re: Re: [mg64583] finding the position of a >>> pattern in list >>> >>> Here is a faster method than the one that I first suggested. >>> >>> pos1[data_]:=Position[Partition[data,2,1],{0,1}]//Flatten; >>> >>> pos2[data_]:=Position[RotateLeft[data]-data,1]//Flatten; >>> >>> data=Table[Random[Integer],{100000}]; >>> >>> pos1[data]==pos2[data] >>> >>> True >>> >>> Timing[pos1[data]][[1]] >>> >>> 0.39032 Second >>> >>> Timing[pos2[data]][[1]] >>> >>> 0.128189 Second >>> >>> >>> Bob Hanlon >>> >>>> >>>> From: Bob Hanlon <hanlonr at cox.net> To: mathgroup at smc.vnet.net >> >>>> Subject: [mg64660] [mg64619] Re: [mg64583] finding the position of a pattern >>>> in list >>>> >>>> data={0,0,1,1,1,0,0,1,1,1,0}; >>>> >>>> Position[Partition[data,2,1],{0,1}]//Flatten >>>> >>>> {2,7} >>>> >>>> >>>> Bob Hanlon >>>> >>>>> >>>>> From: Gang Ma <contactmagang at gmail.com> To: mathgroup at smc.vnet.net >> >>>>> Subject: [mg64660] [mg64619] [mg64583] finding the position of a pattern in >>>>> list >>>>> >>>>> Hi, >>>>> I am working on a program to do the following: My data is a list of 0 >>>>> and 1. For example, {0,0,1,1,1,0,0,1,1,1,0}. I want to find the >>>>> positions of all the pattern of {0,1}. In my previous example, the >>>>> first {0,1} is at 2 and and the second {0,1} appears at 7. I can >>>>> write a loop to do this, but I have several thousands such lists, >>>>> the computation will be time consuming using loop. >>>>> >>>>> My question is whether it is possible to use the pattern match to do >>>>> this quickly. If not for the list, do I need to convert the list to >>>>> string then use some pattern match for string? Thank you very much. >>>>> >>>>> regards, >>>>> >>>>> Gang Ma >>>>> >>>>> >>>>> >>>>> >>>> >>> >>

**References**:**Re: Re: finding the position of a pattern in list (Correction)***From:*Bob Hanlon <hanlonr@cox.net>