Hi all,i need to implement a sliding window function over a list. And i camewith two different implementations:nums:1-100000?1.0;first : { -1 _ y,x}[3 # 0h; nums] /047second: {c: count x; x {x-til 3} each til c} nums /109The value behind the code is the roundtrip time. As you can see thefirst one is two times faster.Can anyone perhaps explain this behaviour? Or can we always say as athump of rule that using scan is in many case faster?CheersKim
> first : { -1 _ y,x}[3 # 0h; nums] /047>> second: {c: count x; x {x-til 3} each til c} nums /109closed form’s even faster{flip count[y]#'(til#'y 0N),'x#enlist y}[3;nums] / 8(also note that “first” is a reserved word, and that you’re joiningshort nulls to a float list in the first example)the specifics of performance in this case, i don’t knowas a general rule, make as much as possible involve vectors–scan isprobably capable of optimizing something based on the fact that you’rereusing the vector from the last iteration.the second solution also has to allocate all 100000 3-element vectorsseparately, which is probably sort of expensive. optimizing the indexgeneration, it’s better than the scan, but still worse than the closedform:{x til[count x]-:til 3}nums / 28
Hi Aaron,thx for your quick reply.On 6 Feb., 10:04, Aaron Davies <aaron.dav…> wrote:> > first : { -1 _ y,x}[3 # 0h; nums] /047>> > second: {c: count x; x {x-til 3} each til c} nums /109>> closed form’s even faster>> {flip count[y]#'(til#'y 0N),'x#enlist y}[3;nums] / 8i can say that your approach is faster than my approach. What do youmean by closed form?>> (also note that “first” is a reserved word, and that you’re joining> short nulls to a float list in the first example)yes, what i mean by first is the first version with implementation. Ithas nothing to do with q.Cheers,Kim>> the specifics of performance in this case, i don’t know>> as a general rule, make as much as possible involve vectors–scan is> probably capable of optimizing something based on the fact that you’re> reusing the vector from the last iteration.>> the second solution also has to allocate all 100000 3-element vectors> separately, which is probably sort of expensive. optimizing the index> generation, it’s better than the scan, but still worse than the closed> form:>> {x til[count x]-:til 3}nums / 28</aaron.dav…>
from ideas above this can also be written slightly more readable
{flip y (til x)+:til (count y)-x }[3;nums]
Hi wp,
very interesting to see that using the 3-element vectors approach
(til x)+:til (count y)-x
you are still very fast. My opinion is that it is the ‘flip’ that
optimizes the procedure.
yes, as aaron said, avoid scans (aka loops) but use operations on vectors.
To: personal-kdbplus@googlegroups.com
X-Mailer: Apple Mail (2.1082)
>> closed form’s even faster
>>
>> {flip count[y]#'(til#'y 0N),'x#enlist y}[3;nums] / 8
>
> i can say that your approach is faster than my approach. What do you =
mean by closed form?
it’s math jargon for a non-iterative solution =
http:
e.g. =
http:o> the “normal” definition of fibonacci is f(1)=1, f(2)=1, =
f(n)=f(n-1)+f(n-2), but the closed form is (phi^n-(1-phi)^n)/sqrt(5), =
where phi=(1+sqrt(5))/2=
</http:></http:>
On Feb 6, 7:46?pm, kuentang <kuent…> wrote:> My opinion is that it is the ‘flip’ that optimizes the procedure.That sounds about right. Although I don’t think there’s any magicinsideflip, it’s just a tight loop that runs without the need to call otherfunctionsinside.In terms of optimization, it looks like q’s compiler doesn’t implementconstantfolding, which would help your 2nd solution to run faster. "til 3"will alwaysevaluate to the same value, which could be moved outside the loop. Onmymachine, there’s almost a 100% speedup for doing so.q)\t second: {c: count x; x {x-til 3} each til c} nums89versusq)\t second: {c: count x; x {x-0 1 2} each til c}47wp’s solution is very elegant. It does produce a slightly differentresult though.</kuent…>
as far as readability i’ve always liked{flip (til x)xprev:y}[3;nums]On Feb 6, 7:27?am, wp <walter1…> wrote:> from ideas above this can also be written slightly more readable>> {flip y (til x)+:til (count y)-x }[3;nums]>>>>>>>> On Sun, Feb 6, 2011 at 11:29 AM, kuentang <kuent…> wrote:>> > Hi Aaron,>> > thx for your quick reply.>> > On 6 Feb., 10:04, Aaron Davies <aaron.dav…> wrote:> >> > first : { -1 _ y,x}[3 # 0h; nums] /047>> >> > second: {c: count x; x {x-til 3} each til c} nums /109>> >> closed form’s even faster>> >> {flip count[y]#'(til#'y 0N),'x#enlist y}[3;nums] / 8>> > i can say that your approach is faster than my approach. What do you> > mean by closed form?>> >> (also note that “first” is a reserved word, and that you’re joining> >> short nulls to a float list in the first example)>> > yes, what i mean by first is the first version with implementation. It> > has nothing to do with q.>> > Cheers,>> > Kim>> >> the specifics of performance in this case, i don’t know>> >> as a general rule, make as much as possible involve vectors–scan is> >> probably capable of optimizing something based on the fact that you’re> >> reusing the vector from the last iteration.>> >> the second solution also has to allocate all 100000 3-element vectors> >> separately, which is probably sort of expensive. optimizing the index> >> generation, it’s better than the scan, but still worse than the closed> >> form:>> >> {x til[count x]-:til 3}nums / 28>> > –> >
Submitted via Google Groups</aaron.dav…></kuent…></walter1…>