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]]]
On your test case we get the correct answer:
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
- References:
- Extracting information from lists
- From: "Tony King" <mathstutoring@ntlworld.com>
- Extracting information from lists