Re: Fast List-Selection
- To: mathgroup at smc.vnet.net
- Subject: [mg19925] Re: [mg19880] Fast List-Selection
- From: "Andrzej Kozlowski" <andrzej at tuins.ac.jp>
- Date: Tue, 21 Sep 1999 02:22:54 -0400
- Sender: owner-wri-mathgroup at wolfram.com
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 >Subject: [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 >Subject: [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? > > >