Re: Re: Pattern Matching in Lists
- To: mathgroup at smc.vnet.net
- Subject: [mg35599] Re: [mg35586] Re: Pattern Matching in Lists
- From: Andrzej Kozlowski <andrzej at platon.c.u-tokyo.ac.jp>
- Date: Mon, 22 Jul 2002 02:10:56 -0400 (EDT)
- Sender: owner-wri-mathgroup at wolfram.com
It now seems to me that I was again premature in stating that Allan's
solution is the "fastest possible". In fact one can construct a hybrid
solution made of my faulty ("cyclic") solution and Allan's solution
which will be on the average faster. Since the cyclic solution fails
only in cases when the first digit is 0 and the last 1, we use it in all
the other cases and switch to Allan's in the unfavorable ones. The
pattern matching needed to do that will cause a slight loss of speed but
still we will be faster on about 3/4 of cases (very slightly of course).
Here is what actually happens:
Here is Allan's solution:
g[l_List] := Count[Drop[l, -1] - Drop[l, 1], 1];
here is the hybrid one:
f[l_List] /; Last[l] â? 1 && First[l] â? 0 := Count[l - RotateLeft[l], 1];
f[l_List] := Count[Drop[l, -1] - Drop[l, 1], 1];
here is our random test generator:
w := Table[Random[Integer], {2000}]
We now see the difference in time used over a 1000 random test runs:
In[5]:=
Block[{x},Plus@@Table[Timing[x=w;(g[x]-f[x])],{1000}]]
Out[5]=
{7.32 Second,0}
Andrzej Kozlowski
Toyama International University
JAPAN
http://platon.c.u-tokyo.ac.jp/andrzej/
On Sunday, July 21, 2002, at 05:50 PM, Andrzej Kozlowski wrote:
> 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}
>>
>>
>>
>> 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
>>>>
>>>>
>>>
>>>
>>>
>>>
>>>
>>>
>>>
>>>
>>
>
>