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: [mg64645] 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:07 -0500 (EST)
  • References: <200602240518.AAA17528@smc.vnet.net> <C187B55A-4417-481E-A6E7-394BCE24F6E5@mimuw.edu.pl> <43FF1C6A.9010109@wolfram.com> <33F64319-9E35-4EF0-AE20-8CF0B616AC7D@gmail.com>
  • Sender: owner-wri-mathgroup at wolfram.com

I guess the easiest way to see what is gong on is to look at a very  
simple example. Consider:

In[1]:=
ls=SparseArray[{0,1,0}]//InputForm

Out[1]//InputForm=
SparseArray[Automatic, {3}, 0, {1, {{0, 1}, {{2}}}, {1}}]

Look at the Output not the Input. Now you should understand what the  
next step does

In[2]:=
ls/.SparseArray[_,_,_,p_]->p

Out[2]//InputForm=
{1, {{0, 1}, {{2}}}, {1}}

Andrzzej Kozlowski

On 24 Feb 2006, at 22:26, Gang Ma wrote:

> 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: [mg64645] [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: [mg64645] [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: [mg64645] [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: Limit
  • Previous by thread: Re: 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)