Re: Re: Pattern Matching in Lists
- To: mathgroup at smc.vnet.net
- Subject: [mg35633] Re: [mg35586] Re: Pattern Matching in Lists
- From: "Fred Simons" <f.h.simons at tue.nl>
- Date: Wed, 24 Jul 2002 02:05:47 -0400 (EDT)
- Sender: owner-wri-mathgroup at wolfram.com
Many postings have appeared how to find the number of occurences (1,0) in a
sequence consisting of zeros and ones. My interest in these postings is
mainly in the various techniques used to solve the problem rather than the
speed of the solution, though I immediately agree that a short and elegant
solution usually is fast as well.
No doubt the shortest and most elegant solution is found by splitting the
list into pairs and simply count the number of lists {1,0}. But that turns
out not to be the fastest solution. The idea behind all other solutions is
to look at the sequence of successive differences and then count the number
1. So how to find this list of differences?
Two ways have been demonstrated:
Drop[lst, -1] - Drop[lst, 1]
Drop[lst - RotateLeft[lst], 1]
These two solutions are about as fast. Andrzej Kozlowsky noted that dropping
the last element in the second solution is only necessary when the list has
the structure {0, ..., 1} which for long lists may give some gain of speed.
There is a third way, as fast as the two others:
ListCorrelate[{1,-1}, lst ]
The list of differences consists of the elements 1, 0 and -1. Instead of
using Count for counting the number of ones, Carl Woll in an ingenious way
replaced the elements -1 by 0 and then used the trace function to count the
number of ones. Successive improvements in the implementation of this idea
bij Allan Hayes and Carl Woll lead to an amazing fast solution by Allan
Hayes.
Still another approach is possible, based on the observation that between
any two occurences of {1,0} in the list there must be an occurence of
{0,1}. Therefore when the list starts with 1 and ends with 0, the number of
1's in the list of diffences is one more than the number of -1's, etc. Using
the same techniques as developed by Carl Woll and Allan Hayes we arrive at
the following solution:
(Tr[BitXor[lst, RotateLeft[lst]]] + If[lst[[1]]==1,
0,If[lst[[-1]]==1, -2,0]]) / 2
Here is a timing for a list of length 5 10^6, compared with Alan's solution:
In[126]:= lst = Table[Random[Integer], {5000000}];
(Tr[lst]-Tr[BitAnd[lst,RotateLeft[lst]]])+
If[lst[[1]]\[Equal]0&&lst[[-1]]\[Equal]1,-1,0]//Timing
(Tr[BitXor[lst, RotateLeft[lst]]]+
If[lst[[1]]\[Equal]1, 0,If[lst[[-1]]\[Equal]1, -2,0]]) / 2 //
Timing
Out[127]=
{1.42 Second,1249704}
Out[128]=
{0.88 Second,1249704}
Fred Simons
Eindhoven University of Technology