Services & Resources / Wolfram Forums
-----
 /
MathGroup Archive
2005
*January
*February
*March
*April
*May
*June
*July
*August
*September
*October
*November
*December
*Archive Index
*Ask about this page
*Print this page
*Give us feedback
*Sign up for the Wolfram Insider

MathGroup Archive 2005

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

Search the Archive

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


  • 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