Hi there,
Any ideas on how to improve the serial or parallel performance of this autocorrelation function? It performs biased (1b) or unbiased (0b) normalization.
acf:{[series;lag;bias]
v:var series;
series-:avg series;
a:{[x;y] sum ((neg y) _ x)*y _x}[series;] peach 1+til lag;
n:(count series)-$[bias;0j;1+til lag];
1f,a%'(n*v)
}
Usage: q) l:“f”$1+til 10
q) acf[l;5;1b]
1 0.7 0.4121212 0.1484848 -0.07878788 -0.2575758
Output for short lists can be verified here
https://www.easycalculation.com/statistics/autocorrelation.php
Scaling is decent going to 2 and 4 threads, with long lists, but I would like
to get a bit more out of the serial implementation especially…
q)l:100000?40.0
q)\ts acf[l;90000;1b] (serial)
14703 6843472
q)\ts acf[l;90000;1b] ( x2 threads)
7450 6683360
Thanks
Nick10
April 22, 2015, 5:15pm
2
the autocorrelation function was discussed in 2011 on the k4 listbox forum available to licensed clients.
the fastest implementation was:
ac:{x%first x:x{(y#x)$neg[y]#x }/:c-til c:count x-:avg x}
it is also discussed on page 54 of the book Q Tips.
the function can be modified to include your three requirements:
limit the number of lags computed (passing 5 returns 5 autocorrelations)
optionally compute unbiased autocorrelations
use peach to make the calculation faster
ac:{x%first x:$[z;::;%[;n]]{(y#x)$neg[y]#x }
q)l:“f”$1+til 10
Excellent Nick. Thank you!
Looks like the dot product ($) is the key to the boost..
If I substitute that in place of sum ()*() I get the same time.