Re: Re: Fast List-Selection
- To: mathgroup at smc.vnet.net
- Subject: [mg19940] Re: [mg19925] Re: [mg19880] Fast List-Selection
- From: "Arnold Knopfmacher" <arnoldk at cam.wits.ac.za>
- Date: Wed, 22 Sep 1999 04:11:19 -0400
- Organization: MS, University of the Witwatersrand
- Sender: owner-wri-mathgroup at wolfram.com
Some Timings for Andrzejs functions applied to the list l=Table[Random[Integer,{0,9}],{100000}]; findsequence[3][l] // Timing {3.51 Second,{{32432}}} findsequence[4][l] // Timing {2.58 Second,32432} findsequence[5][l] // Timing {5.27 Second,32432} Carl Wolls function: rep[ls_,n_]:=Position[Partition[ls,n,1],{x_ ..}] rep[l,6]//Timing {2.47 Second,{{32432}}} Rob Pratts function Consec[l_,n_]:= Flatten[Position[Partition[l,n,1],Table[x_,{n}]]] Consec[l,6]//Timing {2.14 Second,{32432}} My function is still faster (at least for this test list and under Mathematica 3) dif[s_]:=Drop[s,1]-Drop[s,-1]; nconsecB[s_,n_]:= Module[{ss=Flatten[Position[dif[s],0]],ans={}}, Do[If[ss[[i+n-2]]-ss[[i]]==n-2,ans={ans,ss[[i]]}],{i,Length[ss]-n+2}];ans] nconsecB[l,6]//Timing {1.81 Second,{32432}} Perhaps my function can be rewritten in a more elegant form? Arnold Knopfmacher Witwatersrand University South Africa > Date: Tue, 21 Sep 1999 02:22:54 -0400 > Subject: [mg19940] [mg19925] Re: [mg19880] Fast List-Selection > From: "Andrzej Kozlowski" <andrzej at tuins.ac.jp> To: mathgroup at smc.vnet.net > To: mathgroup at smc.vnet.net > I have managed to produce four additional examples, three of which seem to > be faster than yours. I will change the search to 6 rather than 7 > consecutive identical elements because I want to use for my testing a famous > example: > > In[1]:= > l = RealDigits[N[Pi, 10000]][[1]]; > > Hear are the functions I will test, beginning with yours: > > In[2]:= > findsequence[1][l_] := Do[If[Count[t = Take[l, {i, i + 5}], t[[1]]] == 6, > Print[i]], {i, 1, Length[l] - 5}] > > In[3]:= > findsequence[2][l_] := > Position[l /. {a___, y_, y_, y_, y_, y_, y_, b___} -> {a, mark, b}, mark, > 1] > > In[4]:= > findsequence[3][l_] := > Module[{m = Split[l], mark}, > Position[Flatten[m /. Cases[m, _?(Length[#] == 6 &)][[1]] -> mark], > mark, > 1]] > > In[5]:= > findsequence[4][l_] := > Module[{m = Split[l]}, > Length[Flatten[ > Take[m, Position[m, Select[m, Length[#] == 6 &][[1]]][[1, 1]] - > 1]]] + 1] > > In[6]:= > f[x_, x_, x_, x_, x_, x_] := 0; > f[y__] := 1; > g[l_, i_] := f[Apply[Sequence, Take[l, {i, i + 5}]]]; > findsequence[5][l_] := Scan[If[g[l, #] == 0, Return[#]] &, > Range[Length[l]]]; > > Now the test: > > In[9]:= > Table[findsequence[i][l] // Timing, {i, 1, 5}] > 763 > Out[9]= > {{1.38333 Second, > Null}, {2.18333 Second, {{763}}}, {0.783333 Second, {{763}}}, {0.683333 > Second, 763}, {0.183333 Second, 763}} > > The last one wins by a big margin The programs using Split may do better on > other machines (I am using Mac PowerBook G3 ,233 mghz) because there seems > to be something wrong with Split on the Mac where it doesn't scale linearly > with the size of the input. > > Finally: In[10]:= > Take[l, {763, 763 + 5}] > Out[10]= > {9, 9, 9, 9, 9, 9} > -- > Andrzej Kozlowski > Toyama International University > JAPAN > http://sigma.tuins.ac.jp > http://eri2.tuins.ac.jp > > > ---------- > >From: Hans Havermann <haver at total.net> To: mathgroup at smc.vnet.net > To: mathgroup at smc.vnet.net > >To: mathgroup at smc.vnet.net > >Subject: [mg19940] [mg19925] [mg19880] Fast List-Selection > >Date: Mon, Sep 20, 1999, 7:47 AM > > > > > I have a list 's' composed of a large number of (small) integers. I wish to > > search this list for instances of 7 consecutive, identical elements. > > > > My approach is: > > > > Do[If[Count[t = Take[s, {i, i + 6}], t[[1]]] == 7, > > Print[i]], {i, 1, Length[s] - 6}] > > > > Can anyone think of a *faster* way of doing this? > > > > > > > > -- > Andrzej Kozlowski > Toyama International University > JAPAN > http://sigma.tuins.ac.jp > http://eri2.tuins.ac.jp > > > ---------- > >From: Hans Havermann <haver at total.net> To: mathgroup at smc.vnet.net > To: mathgroup at smc.vnet.net > >To: mathgroup at smc.vnet.net > >Subject: [mg19940] [mg19925] [mg19880] Fast List-Selection > >Date: Sun, 19 Sep 1999 18:47:32 -0400 > > > > > I have a list 's' composed of a large number of (small) integers. I wish to > > search this list for instances of 7 consecutive, identical elements. > > > > My approach is: > > > > Do[If[Count[t = Take[s, {i, i + 6}], t[[1]]] == 7, > > Print[i]], {i, 1, Length[s] - 6}] > > > > Can anyone think of a *faster* way of doing this? > > > > > > > >