Re: position of sequence of numbers in list
- To: mathgroup at smc.vnet.net
- Subject: [mg107086] Re: position of sequence of numbers in list
- From: Ray Koopman <koopman at sfu.ca>
- Date: Tue, 2 Feb 2010 03:29:30 -0500 (EST)
- References: <hk17lo$ogf$1@smc.vnet.net> <hk3no0$aib$1@smc.vnet.net>
On Feb 1, 3:10 am, Ray Koopman <koop... at sfu.ca> wrote:
> On Jan 31, 2:58 am, Ray Koopman <koop... at sfu.ca> wrote:
>> On Jan 30, 4:11 am, JB <jke... at gmail.com> wrote:
>>> Hi,
>>>
>>> What is the most efficient way to find the position of the beginning
>>> of a sequence of numbers from a list?
>>>
>>> I found a couple of ways:
>>>
>>> find 3,4 in list={1,2,3,4,5};
>>>
>>> 1. pos=Intersection[Position[list,3],(Position[list,4])+1]
>>>
>>> 2. pos=Position[Partition[list,2,1],{3,4}]
>>>
>>> Are there other ways to do this?
>>> What is the best way when dealing with large lists?
>>>
>>> Thanks,
>>> JB
>>
>> pne[vec,val] returns a list of the positions in vec that are NOT EQUAL
>> to val.
>>
>> peq[vec,val] returns a list of the positions in vec that are EQUAL to
>> val. It's slower than pne but faster than the built-in Position.
>>
>> Both pne and peq return simple lists, not the list-of-lists that
>> Position returns.
>>
>> pne[vec_,val_] := SparseArray[vec,Automatic,val] /.
>> SparseArray[_, _, _, p_] :> Flatten@p[[2,2]]
>>
>> peq[vec_,val_] := Block[{r = Range@Length@vec}, r[[pne[vec,val]]] = 0;
>> SparseArray[r] /. SparseArray[_, _, _, p_] :> p[[3]]]
>>
>> list = Table[Random[Integer,{1,5}],{1*^6}];
>>
>> Timing@Length[a = Intersection[Position[list,3],Position[list,4]-1]]
>> {1.09 Second, 39674}
>>
>> Timing@Length[b = Position[Partition[list,2,1],{3,4}]]
>> {1.4 Second, 39674}
>>
>> Timing@Length[c = Intersection[peq[list,3],peq[list,4]-1]]
>> {0.44 Second, 39674}
>>
>> SameQ[a,b,Transpose@{c}]
>> True
>
> Once we know where the 3's are, we need to look only there for 4's.
> Or we could look for 3's only where there are 4's. The general rule
> would be to look for the less-frequent value first.
>
> Here are some times, incorporating Leonid's observation that
> Position speeds up when it is told to search only level 1.
>
> (Timing the list-generation, with all the other Timing's in the
> same cell, keeps the other times from being overstated. See
> http://groups.google.ca/group/comp.soft-sys.math.mathematica/browse_frm/thread/64cf56831988258a
> )
>
> Timing@Length[list = Table[Random[Integer,{1,5}],{1*^6}]]
> Timing@Length[a = Intersection[Position[list,3],Position[list,4]-1]]
> Timing@Length[b = Position[Partition[list,2,1],{3,4},{1}]]
> Timing@Length[c = Intersection[peq[list,3],peq[list,4]-1]]
> Timing@Length[d = Block[{p3 = peq[Most@list,3]},
> p3[[peq[Rest[list][[p3]],4]]]]]
> SameQ[Flatten@a,Flatten@b,c,d]
>
> {0.84 Second,1000000}
>
> {0.9 Second,39994}
>
> {0.77 Second,39994}
>
> {0.38 Second,39994}
>
> {0.19 Second,39994}
>
> True
One more kick at the can. Method 'e' below is slightly but reliably
faster than 'd', and the code suggests how to generalize to patterns
that are not restricted to adjacent positions in the original list.
Timing@Length[list = Table[Random[Integer,{1,5}],{2*^7}]]
Timing@Length[c = Intersection[peq[list,3],peq[list,4]-1]]
Timing@Length[d = Block[{p3 = peq[Most@list,3]},
p3[[peq[Rest[list][[p3]],4]]]]]
Timing@Length[e = Block[{p3 = peq[Most@list,3]},
p3[[peq[list[[p3+1]],4]]]]]
SameQ[c,d,e]
{13.59 Second, 20000000}
{7.91 Second, 800382}
{4.13 Second, 800382}
{3.8 Second, 800382}
True