Re: Speed Up of Calculations on Large Lists
- To: mathgroup at smc.vnet.net
- Subject: [mg108869] Re: Speed Up of Calculations on Large Lists
- From: Zach Bjornson <bjornson at mit.edu>
- Date: Mon, 5 Apr 2010 08:00:25 -0400 (EDT)
Ray,
Critical statement there is "under your test conditions." I played with
Stefan's problem for quite a while and came up with a few moving average
functions, and tried them all with and without compiling. His function
in particular was only 15% slow compiled/uncompiled on my computer with
his data set. The functions I came up with were usually faster when
compiled, depending on the data set. Also depending on the data set,
some were faster than the built-in MovingAverage function. They were
never faster than the inbuilt function with his data set however, so I
never sent my functions along. Since this came up though, my futzing is
below.
My initial response to Stefen's inquiry was the thought that Compile
would have no effect on MovingAverage, or would just add kernel time
while Mmeca decides to execute it with normal Mathematica code, but I'm
not sure that's true.
-Zach
(*data-set dependencies are illustrated between the top and bottom half
of this*)
$HistoryLength=0 (*to prevent artificially high speeds*)
1.1 Your function
movAverageOwn2FCorig =
Compile[{{dataInput, _Real,
1}, {days, _Integer}, {length, _Integer}},
N[Mean[dataInput[[1 + # ;; days + #]]]] & /@
Range[0, length - days, 1]]
In[165]:=
First@Timing[
Do[movAverageOwn2FCorig[Range[1000000], 2, 1000000];, {10}]]/10
Out[165]= 1.7347
1.2 Inbuilt Mathematica function
In[164]:= First@Timing[Do[MovingAverage[Range[1000000], 2];, {10}]]/10
Out[164]= 1.6942
1.3 My variation #1
movAverageOwn2FCa =
Compile[{{dataInput, _Real, 1}, {days, _Integer}},
Table[Mean[dataInput[[i ;; i + days - 1]]], {i,
Length@dataInput - days + 1}]]
In[166]:=
First@Timing[Do[movAverageOwn2FC[Range[1000000], 2];, {10}]]/10
Out[166]= 1.6146
Non-compiled function version gives a time of 4.0311 for this same data set.
1.4 My variation #2
movAverageOwn2Fb =
Compile[{{dataInput, _Real, 1}, {days, _Integer}},
With[{innerdata = Partition[dataInput, days, 1]},
Table[Mean[innerdata[[i]]], {i, Length@innerdata}]
]]
In[167]:=
First@Timing[Do[movAverageOwn2F3[Range[1000000], 2];, {10}]]/10
Out[167]= 1.6287
Note that this *is* data-set dependent... for example, the same
functions tested on your data symbol give:
In[169]:= First@Timing[Do[MovingAverage[data, 2];, {10}]]/10
Out[169]= 0.0015
In[170]:= First@Timing[Do[movAverageOwn2Fa[data, 2];, {10}]]/10
Out[170]= 0.0171
In[171]:= First@Timing[Do[movAverageOwn2Fb[data, 2];, {10}]]/10
Out[171]= 0.0156
In[173]:=
First@Timing[Do[movAverageOwn2FCorig[data, 2, Length@data];, {10}]]/10
Out[173]= 0.0171
On 4/4/2010 7:45 AM, Ray Koopman wrote:
> Your compiled movAverageC takes 25% more time than the uncompiled
>
> movAv[data_, start_, end_, incr_] := Transpose@PadRight@Join[{data},
> Table[MovingAverage[data, r], {r, start, end, incr}]]
>
> under your test conditions.
>
> On Apr 1, 3:59 am, sheaven<shea... at gmx.de> wrote:
>
>> Hello everyone!
>>
>> I am new to Mathematica and try get a understanding of its power. I
>> plan to use Mathematica mainly for financial data analysis (large
>> lists...).
>>
>> Currently, I am trying to optimize calculation time for calculations
>> based on some sample data. I started with with a moving average of
>> share prices, because Mathematica already has a built in moving
>> average function for benchmarking.
>>
>> I know that the built-in functions are always more efficient than any
>> user built function. Unfortunately, I have to create functions not
>> built in (e.g. something like "moving variance") in the future.
>>
>> I have tried numerous ways to calc the moving average as efficiently
>> as possible. So far, I found that a function based on Span (or
>> List[[x;;y]]) is most efficient. Below are my test results.
>> Unfortunately, my UDF is still more than 5x slower than the built in
>> function.
>>
>> Do you have any ideas to further speed up the function. I am already
>> using Compile and Parallelize.
>>
>> This is what I got so far:
>>
>> 1. Functions for moving average:
>>
>> 1.1. Moving average based on built in function:
>>
>> (*Function calcs moving average based on built in function for
>> specified number of days, e.g. 30 days to 250 days in steps of 10*)
>> movAverageC = Compile[{{inputData, _Real, 1}, {start, _Integer}, {end,
>> _Integer}, {incr, _Integer}}, Module[{data, size, i},
>> size = Length[inputData];
>> Transpose[Join[{inputData}, PadRight[MovingAverage[inputData, #],
>> size]& /@ Table[x, {x, start, end, incr}]]]
>> ]
>> ]
>>
>> 1.2. User defined function based on Span:
>> (*UDF for moving average based on Span*)
>> movAverageOwn2FC = Compile[{{dataInput, _Real, 1}, {days, _Integer},
>> {length, _Integer}},
>> N[Mean[dataInput[[1 + # ;; days + #]]]]& /@ Range[0, length - days,
>> 1]
>> ]
>>
>> (*Function calcs moving average based on UDF "movAverageOwn2FC" for
>> specified number of days, e.g. 30 days to 250 days in steps of 10*)
>> movAverageOwn2C = Compile[{{dataInput, _Real, 1}, {start, _Integer},
>> {end, _Integer}, {incr, _Integer}}, Module[{length},
>> length = Length[dataInput];
>> Transpose[Join[{dataInput}, PadRight[movAverageOwn2FC[dataInput, #,
>> length], length]& /@ Range[start, end, incr]]]
>> ]
>> ]
>>
>> 2. Create sample data:
>> data = 100 + #& /@ Accumulate[RandomReal[{-1, 1}, {10000}]];
>>
>> 3. Test if functions yield same results:
>> Test1 = movAverageC[data, 30, 250, 10]; (*Moving average for 30 days
>> to 250 days in steps of 10*)
>>
>> Test2 = movAverageOwn2C[data, 30, 250, 10]; (*Moving average for 30
>> days to 250 days in steps of 10*)
>>
>> Test1 == Test2
>> Out = True
>>
>> 4. Performance testing (Singe Core):
>> AbsoluteTiming[Table[movAverageC[data, 30, 250, 10], {n, 1, 20, 1}];]
>> (*Repeat function 20x for testing purposes*)
>> Out = {1.3030000, Null}
>>
>> AbsoluteTiming[Table[movAverageOwn2C[data, 30, 250, 10], {n, 1, 20,
>> 1}];] (*Repeat function 20x for testing purposes*)
>> Out = {11.4260000, Null}
>>
>> => Result UDF 9x slower
>>
>> 5. Performance testing (multi core):
>> LaunchKernels[]
>>
>> Out = {KernelObject[1, "local"], KernelObject[2, "local"]}
>>
>> DistributeDefinitions[data, movAverageOwn2C, movAverageOwn2FC,
>> movAverageC]
>>
>> AbsoluteTiming[Parallelize[Table[movAverageC[data, 30, 250, 10], {n,
>> 1, 20, 1}]];]
>> Out = {1.3200000, Null}
>>
>> AbsoluteTiming[Parallelize[Table[movAverageOwn2C[data, 30, 250, 10],
>> {n, 1, 20, 1}]];]
>> Out = {6.7170000, Null}
>>
>> => Result UDF 5x slower
>> Very strange that the built in function does not get faster with
>> Parallelize
>>
>> I would very much appreciate any input on how to decrease calculation
>> time based on the user defined function.
>>
>> Many thanks
>> Stefan
>>
>