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
- References:
- speed of evaluation of an instruction
- From: rudy <rud-x@caramail.com>
- speed of evaluation of an instruction