MathGroup Archive 2006

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

Search the Archive

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
>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>>
>>>>
>>>
>


  • Prev by Date: Re: Re: Re: finding the position of a pattern in list (Correction)
  • Next by Date: Re: Re: Re: finding the position of a pattern in list (Correction)
  • Previous by thread: Re: Re: Re: finding the position of a pattern in list (Correction)
  • Next by thread: Forcing surds into the numerator