MathGroup Archive 1999

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

Search the Archive

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?
>
>
> 


  • Prev by Date: Re: Real roots and other assumptions...
  • Next by Date: Plot, Table.
  • Previous by thread: Re: Fast List-Selection
  • Next by thread: Re: Fast List-Selection