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

**RE: Slow iteration in a functional program**

**Re: Slow iteration in a functional program**

**RE: Re: Re: Pattern Matching in Lists**

**RE: Re: Re: Pattern Matching in Lists**