       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:=
l = RealDigits[N[Pi, 10000]][];

Hear are the functions I will test, beginning with yours:

In:=
findsequence[l_] := Do[If[Count[t = Take[l, {i, i + 5}], t[]] == 6,
Print[i]], {i, 1, Length[l] - 5}]

In:=
findsequence[l_] :=
Position[l /. {a___, y_, y_, y_, y_, y_, y_, b___} -> {a, mark, b}, mark,
1]

In:=
findsequence[l_] :=
Module[{m = Split[l], mark},
Position[Flatten[m /. Cases[m, _?(Length[#] == 6 &)][] -> mark],
mark,
1]]

In:=
findsequence[l_] :=
Module[{m = Split[l]},
Length[Flatten[
Take[m, Position[m, Select[m, Length[#] == 6 &][]][[1, 1]] -
1]]] + 1]

In:=
f[x_, x_, x_, x_, x_, x_] := 0;
f[y__] := 1;
g[l_, i_] := f[Apply[Sequence, Take[l, {i, i + 5}]]];
findsequence[l_] := Scan[If[g[l, #] == 0, Return[#]] &,
Range[Length[l]]];

Now the test:

In:=
Table[findsequence[i][l] // Timing, {i, 1, 5}]
763
Out=
{{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\$B!!(Jbe something wrong with Split on the Mac where it doesn't scale linearly
with the size of the input.

Finally: In:=
Take[l, {763, 763 + 5}]
Out=
{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[]] == 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[]] == 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