Services & ResourcesWolfram ForumsMathGroup Archive

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

Re: Re: Re: finding the position of a pattern in list (Correction)

• To: mathgroup at smc.vnet.net
• Subject: [mg64660] Re: [mg64619] Re: Re: [mg64583] finding the position of a pattern in list (Correction)
• From: "Carl K. Woll" <carlw at wolfram.com>
• Date: Sat, 25 Feb 2006 02:53:21 -0500 (EST)
• References: <200602240518.AAA17528@smc.vnet.net> <C187B55A-4417-481E-A6E7-394BCE24F6E5@mimuw.edu.pl>
• Sender: owner-wri-mathgroup at wolfram.com

Andrzej Kozlowski wrote:
> It is possible to do it still much faster by applying the method  
> advocated a number of times on this list by Carl Woll (who seems to  
> have finally grown tired of doing so I am posting this instead  ;-))
> 
> Here is the Woll approach:
> 
> pos4[l_] := SparseArray[
>   Sign[ListConvolve[{-1,
>       1}, l] + 1] - 1] /. SparseArray[_, _, _, p_] :> Flatten[p[[2,  2]]]
> 
> Let's compare it with pos3 below:
> 
> pos3[data_] := Position[Most[RotateLeft[data]] - Most[data], 1] //  
> Flatten;
> 
> 
> In[3]:=
> data = Table[Random[Integer], {10^5}];
> 
> In[4]:=
> Timing[a = pos4[data]; ]
> 
> Out[4]=
> {0.04354899999999995*Second, Null}
> 
> In[5]:=
> Timing[b = pos3[data]; ]
> 
> Out[5]=
> {0.12303199999999992*Second, Null}
> 
> In[6]:=
> a == b
> 
> Out[6]=
> True
> 

Andrzej,

Thanks for advocating my "method" while I've been attending another 
matter. There's been a new addition to my family, and I've been enjoying 
that.

Concerning your implementation, I would construct the sparse array 
differently, avoiding ListConvolve:

pos5[li_] := Module[{m, r},
   m = Most[li];
   r = Rest[li];
   SparseArray[(r - m)r] /. SparseArray[_,_,_,p_]:>Flatten[p[[2,2]]]
]

Comparing:

d = Table[Random[Integer], {10^6}];

In[22]:=
r1=pos4[d];//Timing
r2=pos5[d];//Timing
r1===r2

Out[22]=
{0.266 Second,Null}

Out[23]=
{0.109 Second,Null}

Out[24]=
True

Carl Woll
Wolfram Research

> 
> Andrzej Kozlowski
> 
> On 24 Feb 2006, at 06:18, Bob Hanlon wrote:
> 
>> There is an error in my second method. It will indicate a match for  
>> the last
>> position if the first data element is 1 and the last data element  is 
>> 0.  For
>> example,
>>
>> pos1[data_]:=Position[Partition[data,2,1],{0,1}]//Flatten;
>>
>> pos2[data_]:=Position[RotateLeft[data]-data,1]//Flatten;
>>
>> data={1,0,0,1,0,0,1,0};
>>
>> pos1[data]
>>
>> {3,6}
>>
>> pos2[data]
>>
>> {3,6,8}
>>
>> The correct method is
>>
>> pos3[data_]:=Position[Most[RotateLeft[data]]-Most[data],1]//Flatten;
>>
>> pos3[data]
>>
>> {3,6}
>>
>> The revision is still much faster than the original.
>>
>> data=Table[Random[Integer],{100000}];
>>
>> pos1[data]==pos3[data]
>>
>> True
>>
>> Timing[pos1[data]][[1]]
>>
>> 0.389007 Second
>>
>> Timing[pos3[data]][[1]]
>>
>> 0.132175 Second
>>
>>
>> Bob Hanlon
>>
>>>
>>> From: Bob Hanlon <hanlonr at cox.net>
To: mathgroup at smc.vnet.net
>>
>>> Subject: [mg64660] [mg64619] Re: Re: [mg64583] finding the position of a  
>>> pattern in list
>>>
>>> Here is a faster method than the one that I first suggested.
>>>
>>> pos1[data_]:=Position[Partition[data,2,1],{0,1}]//Flatten;
>>>
>>> pos2[data_]:=Position[RotateLeft[data]-data,1]//Flatten;
>>>
>>> data=Table[Random[Integer],{100000}];
>>>
>>> pos1[data]==pos2[data]
>>>
>>> True
>>>
>>> Timing[pos1[data]][[1]]
>>>
>>> 0.39032 Second
>>>
>>> Timing[pos2[data]][[1]]
>>>
>>> 0.128189 Second
>>>
>>>
>>> Bob Hanlon
>>>
>>>>
>>>> From: Bob Hanlon <hanlonr at cox.net>
To: mathgroup at smc.vnet.net
>>
>>>> Subject: [mg64660] [mg64619] Re: [mg64583] finding the position of a  pattern 
>>>> in list
>>>>
>>>> data={0,0,1,1,1,0,0,1,1,1,0};
>>>>
>>>> Position[Partition[data,2,1],{0,1}]//Flatten
>>>>
>>>> {2,7}
>>>>
>>>>
>>>> Bob Hanlon
>>>>
>>>>>
>>>>> From: Gang Ma <contactmagang at gmail.com>
To: mathgroup at smc.vnet.net
>>
>>>>> Subject: [mg64660] [mg64619] [mg64583] finding the position of a pattern  in 
>>>>> list
>>>>>
>>>>> Hi,
>>>>> I am working on a program to do the following: My data is a list  of 0
>>>>> and 1. For example, {0,0,1,1,1,0,0,1,1,1,0}. I want to find the
>>>>> positions of all the pattern of {0,1}.  In my previous example, the
>>>>> first {0,1} is at 2 and and the second {0,1} appears at 7. I can
>>>>> write a loop to do this, but I have several thousands such lists,
>>>>> the computation will be time consuming using loop.
>>>>>
>>>>> My question is whether it is possible to use the pattern match  to do
>>>>> this quickly.  If not for the list, do I need to convert the  list to
>>>>> string then use some pattern match for string?  Thank you very  much.
>>>>>
>>>>> regards,
>>>>>
>>>>> Gang Ma
>>>>>
>>>>>
>>>>>
>>>>>
>>>>
>>>
>>

• References:
  • Re: Re: finding the position of a pattern in list (Correction)
    • From: Bob Hanlon <hanlonr@cox.net>