MathGroup Archive 2006

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

Search the Archive

Re: speed of evaluation of an instruction

  • To: mathgroup at smc.vnet.net
  • Subject: [mg65033] Re: [mg64961] speed of evaluation of an instruction
  • From: Carl Woll <carlw at wolfram.com>
  • Date: Sun, 12 Mar 2006 23:57:51 -0500 (EST)
  • References: <200603101014.FAA21887@smc.vnet.net>
  • Sender: owner-wri-mathgroup at wolfram.com

rudy wrote:

>hello,
>
>To sort a list I utilize these instructions:
>
>t = Split[testList];
>t = t /. x : {1 ..} :> {1, Rest[x] /. 1 -> 0} // Flatten;
>Position[t, 1] // Flatten; 
>
>But there's something I don't understand at all.
>If I do:
>
>In > testList = Table[Random[Integer], {100000}];
>
>In > t = Split[testList];
>     t = t /. x : {1 ..} :> {1, Rest[x] /. 1 -> 0} // Flatten;
>     Position[t, 1] // Flatten; // Timing
>  
>
Notice that you are only timing the Position[t,1] statement. You are not 
including the time it takes to Split testList and then to do the 
replacement. This explains all of the timing "discrepancies" you mention 
below.

>Out > {0.062 Second, Null}
>
>cool: it's quick!... but if I do then: 
>
>In > rapid[l_List] := Module[{t = Split[l], x, res},
>     t = t /. x : {1 ..} :> {1, Rest[x] /. 1 -> 0} // Flatten;
>     res = Position[t, 1] // Flatten]
>
>In > rapid[testList];//Timing
>
>Out > {0.344 Second, Null}
>
>It's 5 times slower...!?
>Nevertheless the only difference between the two cases is in the second the instruction is executed inside a Module...
>
>That's not all:
>We should think this is caused by the fact we execute an instruction inside a function ("rapid"), but if we do:
>
>In > Position[
>              Split[testList] /.
>                                 x : {1 ..} :> 
>                                            {1, Rest[x] /. 1 -> 0} 
>                                            // Flatten, 1
>             ] // Flatten; // Timing
>
>Out > {0.468 Second, Null}
>
>It's again slower!...
>
>Could anybody expalin this ?
>Thanks all
>Rudy
>  
>
If you are interested in finding the positions of the first 1 in a run 
of 1s, the following function will probably be much faster:

runpos[data_] := Module[{},
nonzeropositions[
UnitStep[data - PadRight[data, Length[testList], 0, 1] - 1]
]
]

nonzeropositions[data_] :=
SparseArray[data] /. SparseArray[_, _, _, p_] :> Flatten[p[[2, 2]]]

With the data:

testList = Table[Random[Integer], {10^6}];

We have:

In[48]:=
r1=Position[
Split[testList]/.x:{1..}:>{1,Rest[x]/.1->0}//Flatten,1]//
Flatten;//Timing
r2=runpos[testList];//Timing
r1===r2

Out[48]=
{2.282 Second,Null}

Out[49]=
{0.125 Second,Null}

Out[50]=
True



  • Prev by Date: Using pictures instead of symbols in an equation.
  • Next by Date: Re: Fastest method for comparing overlapping times in random time series
  • Previous by thread: speed of evaluation of an instruction
  • Next by thread: Re: speed of evaluation of an instruction