Re: Extracting information from lists

• To: mathgroup at smc.vnet.net
• Subject: [mg63360] Re: [mg63323] Extracting information from lists
• From: "Carl K. Woll" <carlw at wolfram.com>
• Date: Sun, 25 Dec 2005 02:19:37 -0500 (EST)
• References: <200512241218.HAA15938@smc.vnet.net>
• Sender: owner-wri-mathgroup at wolfram.com

```Tony King wrote:
> Does anyone know of a function that will allow me to extract the positions
> of the first elements of runs of similar elements within a list. For
> example, suppose that
>
> list={7,9,1,6,8,1,1,6,5,1,1,1,8,7,6,1,1,1,1,7}
>
> I need a function that will return
>
> {3,6,10,16}
>
> corresponding to the runs {1},{1,1},{1,1,1},{1,1,1,1} within list
>
> Many thanks
>
> Tony

For very long lists, the most efficient method is probably something like:

1. convert all integers other than 1 to 0.
2. look for a 0 followed by a 1 by using BitAnd and BitXor.

The following function carries out this idea, except that I convert 1->0
and all other integers to 1:

runpos[d_] := Module[{m = Sign[Abs[d - 1]]},
SparseArray[BitAnd[Prepend[Most[m], 1], BitXor[1, m]]]] /.
SparseArray[_, _, _, a_] :> Flatten[a[[2, 2]]]

In[12]:=
runpos[list]
Out[12]=
{3,6,10,16}

For a random list of 10^6 integers, we get:

In[13]:=
data=Table[Random[Integer,{1,10}],{10^6}];

In[14]:=
runpos[data];//Timing
Out[14]=
{0.094 Second,Null}

For comparison purposes, note that runpos is significantly faster than
Split:

In[15]:=
Split[data];//Timing
Out[15]=
{0.562 Second,Null}

Any method which first splits the data will be much slower than runpos.
A different approach using Compile may be faster.

Carl Woll
Wolfram Research

```

• Prev by Date: Re: Extracting information from lists
• Next by Date: Re: Extracting information from lists
• Previous by thread: Extracting information from lists
• Next by thread: Re: Extracting information from lists