RE: Re: Re: Pattern Matching in Lists
- To: mathgroup at smc.vnet.net
- Subject: [mg35626] RE: [mg35597] Re: [mg35586] Re: Pattern Matching in Lists
- From: "DrBob" <majort at cox-internet.com>
- Date: Tue, 23 Jul 2002 01:51:38 -0400 (EDT)
- Reply-to: <drbob at bigfoot.com>
- Sender: owner-wri-mathgroup at wolfram.com
f5 (uncompiled) is about 2.5 times faster than f7 (compiled):
Needs["Statistics`HypothesisTests`"]
f1[w_] := Count[Partition[w, 2, 1], {1, 0}]
f2[w_] := Count[Drop[w, -1] - Drop[w, 1], 1] (* Allan Hayes *)
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]
f6[w_] := (Tr[#] - Tr[# Drop[w, 1]]) &[Drop[w, -1]]
(* Andrzej Kozlowski *)
f7 = Compile[{{w, _Integer, 1}}, Count[Drop[w, -1] - Drop[w, 1], 1]];
f8[w_List] /; Last[w] == 1 && First[w] == 0 := Count[w - RotateLeft[w],
1];
f8[w_List] := Count[Drop[w, -1] - Drop[w, 1], 1];
trial[f_, g_] := (n = 2000000; w = Table[Random[Integer], {n}];
First@Timing[#[w];]/Second & /@ {f, g}
)
test[f_, g_, n_Integer] := (
{t1, t2} = Transpose[trial[f, g] & /@ Range[n]];
Print[Mean /@ {t1, t2}];
Print[r = MeanTest[t1 - t2, 0, FullReport -> True]];
meanDiff = (FullReport /. r)[[1, 1, 1]];
Print["% difference = ", meanDiff/Mean[t1]])
test[f7, f5, 5]
{0.12759999999999536, 0.07240000000000464}
{FullReport -> TableForm[{{"Mean", "TestStat", "Distribution"},
{0.05519999999999072, 5.2573812925427745,
StudentTDistribution[4]}}, TableHeadings ->
{None, {"Mean", "TestStat", "Distribution"}}],
OneSidedPValue -> 0.0031328222915485435}
% difference = 0.4326018808
Meanwhile, f5 is about 9 times faster than f8:
test[f8, f5, 10]
{0.5876000000000033, 0.06890000000000214}
{FullReport -> TableForm[{{"Mean", "TestStat", "Distribution"},
{0.5187000000000012, 37.84563407920352,
StudentTDistribution[9]}},
TableHeadings -> {None, {"Mean", "TestStat", "Distribution"}}],
OneSidedPValue -> 1.558006714008781*^-11}
% difference = 0.8827433628
Bobby Treat
-----Original Message-----
From: Andrzej Kozlowski [mailto:andrzej at platon.c.u-tokyo.ac.jp]
To: mathgroup at smc.vnet.net
Subject: [mg35626] [mg35597] Re: [mg35586] Re: Pattern Matching in Lists
I was too quick with sending my alleged solution , not noticing
immediately that it fails in cases when w is of the form {0,...,1}. (It
works however if we consider "cyclic" solutions, meaning that {0,1} is
thought to contain one instance of {1,0}!)
Since there seems no way of dealing with this problem without making the
solutions slower, Alan's
Count[Drop[w,-1]-Drop[w,1],1]
is indeed (almost certainly) the fastest solution.
(of course one can still make it faster by compiling:
f = Compile[{{w, _Integer, 1}}, Count[Drop[w, -1] - Drop[w, 1], 1]]
is about 6 times faster on my machine than the uncompiled version).
Andrzej
On Sunday, July 21, 2002, at 04:48 PM, Andrzej Kozlowski wrote:
> Having quickly glanced through the avalanche of proposed solutions I
> did not see following one.(if there was I apologize for claiming it as
> my own):
>
> Count[w - RotateLeft[w], 1]
>
> According to my comparisons it is the fastest so far (the one that I
> sent originally is one of the slowest)
>
> In[1]:=
> w=Table[Random[Integer],{200000}];
>
> In[2]:=
> Count[Partition[w,2,1],{1,0}]//Timing
>
> Out[2]=
> {0.86 Second,50131}
>
> In[3]:=
> Count[Drop[w,-1]-Drop[w,1],1]//Timing
>
> Out[3]=
> {0.34 Second,50131}
>
> In[5]:=
> Count[w-RotateLeft[w],1]//Timing
>
> Out[5]=
> {0.29 Second,50131}
>
Andrzej Kozlowski
Toyama International University
JAPAN
http://platon.c.u-tokyo.ac.jp/andrzej/
>
>
> On Sunday, July 21, 2002, at 02:01 PM, Allan Hayes wrote:
>
>> [second posting in view of reported technical problem]
>>
>> Anthony,
>> Take
>> w = Table[Random[Integer], {200000}
>>
>> My first thought was, and several posts used this,
>>
>> Count[Partition[w, 2,1],{1,0}]//Timing
>>
>> {3.24 Second,49851}
>>
>> Later it occured to me to use arithmetic, which turned out to be
twice
>> as
>> fast:
>>
>> Count[ Drop[w,-1] - Drop[w,1],1]//Timing
>>
>> {1.49 Second,49851}
>>
>> This is close to Selwyn Hollis's code
>>
>> Count[Drop[w+2RotateRight[w],1],2]//Timing
>>
>> {1.6 Second,49851}
>>
>> --
>> 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
>>
>>
>> "Anthony Mendes" <amendes at zeno.ucsd.edu> wrote in message
>> news:ah5qce$59o$1 at smc.vnet.net...
>>> Hello,
>>>
>>> Suppose w={1,1,1,0,0,1,0,1,0,0,1,0,0}.
>>>
>>> How can I count the number of occurrences of a 1 in w immediately
>>> followed by a 0 in w?
>>>
>>> I have tried every incarnation of Count[] I can think of; for
example,
>>>
>>> Count[w,{___,1,0,___}]
>>>
>>> does not seem to work. In general, how can I count the number of
>>> occurrences of a 1 followed by a 0 in a list of 1's and 0's? Thank
>>> you!
>>>
>>>
>>> --
>>> Tony
>>> _____________________
>>> amendes at math.ucsd.edu
>>>
>>>
>>
>>
>>
>>
>>
>>
>>
>>
>