Re: Re: Re: list manipulation

• To: mathgroup at smc.vnet.net
• Subject: [mg20688] Re: [mg20614] Re: [mg20601] Re: list manipulation
• From: "Allan Hayes" <hay at haystack.demon.co.uk>
• Date: Sun, 7 Nov 1999 02:10:18 -0500
• Sender: owner-wri-mathgroup at wolfram.com

```Hartmut,

We can speed things up by avoiding AppendTo and constructing "linked lists"

{}, {{},1}, {{{},1},2}, {{{{},1},2},3}, ......... {.,n}

To be flattend to {1,2,......,n} at the end.
This is a generally applicable trick.

A slight extra speedup come from accumulatig positions instead of elements.

The timings on my machine for the case of 10000 events comes down from

to 5.33 Second, 5.16 Second and 4.94 Second

in the variants below.

Function[{n},
gapsX[n] =
Module[{kappa = 250./n},
Table[With[{c = Random[Real, {0., 100.}],
d = kappa Exp[-Random[Real, {0., 10.}]]}, {c - d,
c + d}], {n}]];
{Timing[truegapsX[n] =
Interval @@
gapsX[n];]\[LeftDoubleBracket]1\[RightDoubleBracket],
Length[truegapsX[n]]}] /@ {100, 300, 1000, 3000, 10000}

{{0. Second, 62}, {0.11 Second, 178}, {0.55 Second, 582}, {6.75 Second,
1821}, {91.34 Second, 6006}}

Function[{n}, events[n] = Table[Random[Real, 100.], {n}];] /@ {100, 300,
1000,
3000, 10000};

********* Helmut Wolf ********

(Function[n, ((Print[#1]; #1) & )[
Timing[ss[n] = Module[{selected = {}, t = 1},
With[{tmax = Length[events[n]],
events = Sort[events[n]], gaps =
truegapsX[n]},
Do[While[t <= tmax && events[[t]] < gaps[[i,
1]], AppendTo[selected, events[[
t++]]]]; While[t <= tmax && events[[
t]] <= gaps[[i,2]], t++],
{i, 1, Length[gaps]}]; Join[selected,
Take[events, {t, tmax}]]]]; ][[1]]]]) /@
{100, 300, 1000, 3000, 10000}

0.06 Second

0.38 Second

0.93 Second

5.94 Second

70.52 Second

{0.06 Second, 0.38 Second, 0.93 Second, 5.94 Second, 70.52 Second}

****** Allan Hayes variants *********

(Function[n, ((Print[#1]; #1) & )[
Timing[ss1[n] = Module[{selected = {}, t = 1},
With[{tmax = Length[events[n]],
events = Sort[events[n]], gaps =
truegapsX[n]},
Do[While[t <= tmax && events[[t]] < gaps[[i,
1]], selected = {selected, events[[
t++]]}]; While[t <= tmax && events[[
t]] <= gaps[[i,2]], t++],
{i, 1, Length[gaps]}]; Join[Flatten[
selected], Take[events, {t, tmax}]]]]; ][[
1]]]]) /@ {100, 300, 1000, 3000, 10000}

0.06 Second

0.38 Second

0.55 Second

1.65 Second

5.33 Second

{0.06 Second, 0.38 Second, 0.55 Second, 1.65 Second, 5.33 Second}

** Linked Lists and accumulating positions

(Function[n, ((Print[#1]; #1) & )[
Timing[ss2[n] = Module[{selected = {}, t = 1},
With[{tmax = Length[events[n]],
events = Sort[events[n]], gaps =
truegapsX[n]},
Do[While[t <= tmax && events[[t]] < gaps[[i,
1]], selected = {selected, t}; t++];
While[t <= tmax && events[[t]] <= gaps[[i,
2]], t++], {i, 1, Length[gaps]}];
Join[events[[Flatten[selected]]],
Take[events, {t, tmax}]]]]; ][[1]]]]) /@
{100, 300, 1000, 3000, 10000}

0.05 Second

0.39 Second

0.44 Second

1.7 Second

5.16 Second

{0.05 Second, 0.39 Second, 0.44 Second, 1.7 Second, 5.16 Second}

positions of unwanted elements

(Function[n, ((Print[#1]; #1) & )[
Timing[ss3[n] = Module[{t = Length[events[n]],
se = Sort[events[n]], gaps = truegapsX[n],
bag = {}},
Do[While[t > 0 && se[[t]] > gaps[[i,2]], --t];
While[t > 0 && se[[t]] >= gaps[[i,1]],
bag = {bag, t}; --t], {i, Length[gaps], 1,
-1}]; Delete[se, List /@ Flatten[bag]]]][[
1]]]]) /@ {100, 300, 1000, 3000, 10000}

0.05 Second

0.33 Second

0.6 Second

1.6 Second

4.94 Second

{0.05 Second, 0.33 Second, 0.6 Second, 1.6 Second, 4.94 Second}

********* Check Correctness ***********

ss[100] === ss1[100] === ss2[100] === ss3[100]

True

ss[300] === ss1[300] === ss2[300] === ss3[300]

True

ss[1000] === ss1[1000] === ss2[1000] === ss3[1000]

True

ss[3000] === ss1[3000] === ss2[3000] === ss3[3000]

True

ss[10000] === ss1[10000] === ss2[10000] === ss3[10000]

True

Allan
---------------------
Allan Hayes
Mathematica Training and Consulting
Leicester UK
www.haystack.demon.co.uk
hay at haystack.demon.co.uk
Voice: +44 (0)116 271 4198
Fax: +44 (0)870 164 0565

```

• Prev by Date: Re: Re: Combinatorica questions!!!
• Next by Date: Re: RE: Bug in math4
• Previous by thread: Re: Re: Re: list manipulation
• Next by thread: Re: Re: Re: Re: list manipulation