[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
>>>>
>>>>
>>>>
>>>>
>>>
>>
>
Prev by Date:
**Re: 3D Graphics suggestions?**
Next by Date:
**Re: Re: Re: finding the position of a pattern in list (Correction)**
Previous by thread:
**Re: Re: finding the position of a pattern in list (Correction)**
Next by thread:
**Re: Re: Re: finding the position of a pattern in list (Correction)**
| |