MathGroup Archive 2010

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

Search the Archive

Re: position of sequence of numbers in list

  • To: mathgroup at smc.vnet.net
  • Subject: [mg107027] Re: position of sequence of numbers in list
  • From: Ray Koopman <koopman at sfu.ca>
  • Date: Mon, 1 Feb 2010 06:10:12 -0500 (EST)
  • References: <hk17lo$ogf$1@smc.vnet.net> <hk3no0$aib$1@smc.vnet.net>

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


  • Prev by Date: Re: Numerical Problem
  • Next by Date: Re: solving equations with BitXor
  • Previous by thread: Re: Re: Re: Numerical Problem
  • Next by thread: Re: position of sequence of numbers in list