Services & ResourcesWolfram ForumsMathGroup Archive

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

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
• References: <199911020735.CAA26984@smc.vnet.net.> <199911040713.CAA02648@smc.vnet.net.> <3822F4DD.4A5EA11A@gsmail01.darmstadt.dsh.de>
• 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

70.52 Second for your function

to 5.33 Second, 5.16 Second and 4.94 Second

in the variants below.



 ***** Your Test Data *****

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

** Using linked lists

(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}

** Linked lists and working backwards - start with full bag and find
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

• Follow-Ups:
  • Re: Re: Re: Re: list manipulation
    • From: Daniel Lichtblau <danl@wolfram.com>

• References:
  • Re: list manipulation
    • From: "jim leddon" <jleddon@home.com>
  • Re: Re: list manipulation
    • From: "Wolf, Hartmut" <hwolf@debis.com>