MathGroup Archive 2002

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

Search the Archive

RE: Re: Pattern Matching in Lists

  • To: mathgroup at smc.vnet.net
  • Subject: [mg35614] RE: [mg35607] Re: Pattern Matching in Lists
  • From: "DrBob" <majort at cox-internet.com>
  • Date: Tue, 23 Jul 2002 01:51:10 -0400 (EDT)
  • Reply-to: <drbob at bigfoot.com>
  • Sender: owner-wri-mathgroup at wolfram.com

Amazing!  f5 is three times as fast as the previous best (f4), which was
three times as fast as f3:

Needs["Statistics`HypothesisTests`"]
f1[w_] := Count[Partition[w, 2, 1], {1, 0}]
f2[w_] := Count[Drop[w, -1] - Drop[w, 1], 1]
f3[w_] := Count[Drop[w + 2RotateRight[w], 1], 2]
f4[w_] := Tr[Drop[w, -1](Drop[w, -1] - Drop[w, 1])]
f5[w_] := (Tr[w] - Tr[BitAnd[w, RotateLeft[w]]]) + If[w[[
    1]] == 0 && w[[-1]] == 1, -1, 0]
trial := (n = 2000000; w = Table[Random[Integer], {n}];
First@Timing[#[w];]/Second & /@ {f4, f5}
    )

{t1, t2} = Transpose[trial & /@ Range[30]];
Mean /@ {t1, t2}
r = MeanTest[t1 - t2, 0, FullReport -> True]
meanDiff = (FullReport /. r)[[1, 1, 1]];
Print["% difference = ", meanDiff/Mean[t1]]

{0.21470000000000045, 0.07439999999999972}
{FullReport -> TableForm[
    {{"Mean", "TestStat", "Distribution"}, 
     {0.14030000000000073, 25.617955788393118, 
      StudentTDistribution[29]}}, 
    TableHeadings -> 
     {None, {"Mean", "TestStat", "Distribution"}}], 
  OneSidedPValue -> 9.108095822591074*^-22}

% difference = 0.6534699580

Bobby Treat

-----Original Message-----
From: Allan Hayes [mailto:hay at haystack.demon.co.uk] 
To: mathgroup at smc.vnet.net
Subject: [mg35614] [mg35607] Re: Pattern Matching in Lists

Adding Andrzej's idea using a single rotation with correction to Carl's
latest gives a further speed up:

    w=Table[Random[Integer],{1000000}];

    (Tr[#]-Tr[BitAnd[# ,Drop[w,1]]])&[Drop[w,-1] ]//Timing

        {2.36 Second,249981}

    (Tr[w]-Tr[BitAnd[w ,RotateLeft[w]]])+
        If[w[[1]]==0&&w[[-1]]==1,-1,0]//Timing

        {1.43 Second,249981}

--
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: Memory leak? Self-created non-executable Help notebook?
  • Next by Date: RE: Re: Pattern Matching in Lists
  • Previous by thread: Re: Re: Pattern Matching in Lists
  • Next by thread: RE: Re: Pattern Matching in Lists