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: [mg64658] Re: [mg64619] Re: Re: [mg64583] finding the position of a pattern in list (Correction)
• From: Andrzej Kozlowski <akoz at mimuw.edu.pl>
• Date: Sat, 25 Feb 2006 02:53:19 -0500 (EST)
• References: <200602240518.AAA17528@smc.vnet.net>
• Sender: owner-wri-mathgroup at wolfram.com

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 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: [mg64658] [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: [mg64658] [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: [mg64658] [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>