Services & ResourcesWolfram ForumsMathGroup Archive

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

Re: position of sequence of numbers in list

• To: mathgroup at smc.vnet.net
• Subject: [mg107003] Re: [mg106976] position of sequence of numbers in list
• From: Leonid Shifrin <lshifr at gmail.com>
• Date: Sun, 31 Jan 2010 05:57:37 -0500 (EST)
• References: <201001301212.HAA25132@smc.vnet.net>

Hi,

Partition is in fact pretty good. In case you need only the first entry of
your sublist (rather than all), you can speed it up by indicating that only
one result is needed:

Position[Partition[list, 2, 1], {3, 4}, 1, 1]

{{3}}

Exactly how much faster this will run will depend on how early in the first
list the first instance of the second list  is located.

If you will be dealing with numbers (integers or reals), you can get  quite
a substantial speedup (for a single first entry search) by going back to
good old procedural approach (Compiled however), since this avoids the
overhead of Partition (however small it may be, it is proportional to the
length of the list, while procedural approach's complexity is proportional
to the value of the first position of your sequence):

posf = Compile[{{lst, _Integer, 1}, {target, _Integer, 1}},
  Module[{i = 1, j = 1},
   For[i = 1, i <= Length[lst], i++,
    If[lst[[i]] == target[[j]], j++, j = 1];
    If[j == Length[target] + 1, Return[i - j + 2]]];
   Return[-1]]]


largeTest = RandomInteger[{1, 200}, 300000];

Position[Partition[largeTest , 2, 1], {3, 4}, 1, 1] // Timing

{0.231, {{46488}}}

Position[Partition[largeTest , 2, 1], {3, 4}] // Timing

{0.42, {{46488}, {94012}, {110753}, {125158}, {208861}, \
{243203}, {263641}, {273780}}}

posf[largeTest , {3, 4}] // Timing

{0.04, 46488}

Again, the speedup rate will depend on how early in the list the result is
first located.

Hope this helps.

Regards,
Leonid


On Sat, Jan 30, 2010 at 4:12 AM, JB <jkerrb 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
>
>

• References:
  • position of sequence of numbers in list
    • From: JB <jkerrb@gmail.com>