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
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>
>>>>>
>>>>
>>
>
- References:
- Re: Re: finding the position of a pattern in list (Correction)
- From: Bob Hanlon <hanlonr@cox.net>
- Re: Re: finding the position of a pattern in list (Correction)