Re: Re: Re: finding the position of a pattern in list (Correction)
- To: mathgroup at smc.vnet.net
- Subject: [mg64662] Re: [mg64619] Re: Re: [mg64583] finding the position of a pattern in list (Correction)
- From: Gang Ma <contactmagang at gmail.com>
- Date: Sat, 25 Feb 2006 02:53:24 -0500 (EST)
- Sender: owner-wri-mathgroup at wolfram.com
Hi,all,
Thank for all your answers to my question. All your methods are
great, I learned a lot from them. Since Carl's solution is the
fastest one, I will use it. However, its syntax is a bit mysterious
for me, in particular the rule used in Carl SparseArray[_, _, _,
p_] :> Flatten[p[[2, 2]]]. I checked the reference and found that
SparseArray can have three arguments: data,dims, val. (Page 296 of
Mathematica book 5th version) . But in Carl's rule, it has fourth
arguments and the fourth one p is quite important.
Could any of you give me more explanation for this rule? Thank you
very much.
regards,
Gang Ma
On Feb 24, 2006, at 9:47 AM, Carl K. Woll wrote:
> 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: [mg64662] [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: [mg64662] [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: [mg64662] [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
>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>>
>>>>
>>>
>