Thomas wrote:
> I am actually more encouraged now about the prospects of O.
This is a performance comparison of a classic, tail recursive, and a TCO
versions of factorial:
NB. Factorial...
fact =. 1:`(* $:@<:)@.(1&<) NB. Classic
tail =. (* , <:@:])/
FactTailCore=. ]`($:@:tail)@.(1 < {:)
( Fact =. {. @: FactTailCore @: (1&,)f. ) NB. Tail
recursive (fixed)
{.@:(]`($:@:((* , <:@:])/))@.(1 < {:) (103!:0))@:(1&,)
FactTCO=. {.@:(]`($:@:((* , <:@:])/))@.(1 < {:)O.)@:(1&,) NB. Tail
recursive optimized (fixed)
st=. (] , <@:(1&({::) * 2&({::)))@:(] ; 7!:2@:] ; 6!:2)
10 st &> 'fact 11x' ; 'Fact 11x' ; 'FactTCO 11x'
┌─────────────┬─────┬──────────┬────────┐
│fact 11x │12544│2.47973e_5│0.311057│
├─────────────┼─────┼──────────┼────────┤
│Fact 11x │9216 │4.14501e_5│0.382005│
├─────────────┼─────┼──────────┼────────┤
│FactTCO 11x│4608 │4.15826e_5│0.191613│
└─────────────┴─────┴──────────┴────────┘
10 st &> 'fact 111x' ; 'Fact 111x' ; 'FactTCO 111x'
┌─────────────┬──────┬───────────┬───────┐
│fact 111x │114944│0.000238305│27.3918│
├─────────────┼──────┼───────────┼───────┤
│Fact 111x │102400│0.000391922│40.1329│
├─────────────┼──────┼───────────┼───────┤
│FactTCO 111x│5504 │0.000417481│2.29782│
└─────────────┴──────┴───────────┴───────┘
10 st &> 'fact 1111x' ; 'Fact 1111x' ; 'FactTCO 1111x'
┌─────────────┬───────┬──────────┬───────┐
│fact 1111x │1204480│0.00392512│4727.72│
├─────────────┼───────┼──────────┼───────┤
│Fact 1111x │5957888│0.00380798│22687.5│
├─────────────┼───────┼──────────┼───────┤
│FactTCO 1111x│28544 │0.00374137│106.794│
└─────────────┴───────┴──────────┴───────┘
At this point we need to bring another kind of contenders:
5 st &> '(*/ @: >: @: i.)11111x' ; '! 11111x' ; 'FactTCO 11111x'
┌──────────────────────┬───────┬────────┬─────────┐
│(*/ @: >: @: i.)11111x│3815680│0.262486│1.00156e6│
├──────────────────────┼───────┼────────┼─────────┤
│! 11111x │2163456│0.262986│568958 │
├──────────────────────┼───────┼────────┼─────────┤
│FactTCO 11111x │397184 │0.273211│108515 │
└──────────────────────┴───────┴────────┴─────────┘
So far that is not bad, not bad at all.
On Wed, Aug 27, 2014 at 4:59 PM, Thomas Costigliola <[email protected]>
wrote:
> quicksort won't work with O. The good news is that I doubt the function
> call depth will be a limiting factor with quicksort since I believe the
> depth will grow roughly proportional to log N. It is possible to
> reformulate it to work with O. which *may* provide some speed benefit, but
> will that resulting form be too unintuitive to justify the benefits? Maybe.
> I will give it a try.
>
>
> On Wed, Aug 27, 2014 at 4:27 PM, 'Pascal Jasmin' via Programming <
> [email protected]> wrote:
>
> > I think O. would be useful. Tree spanning algorithms such as quicksort,
> I
> > don't think I could do well without $:
> >
> > for reference,
> >
> > quicksort=: (($:@(<#[), (=#[), $:@(>#[)) ({~ ?@#)) ^: (1<#)
> >
> > Does O. work on it?
> >
> >
> > ----- Original Message -----
> > From: Thomas Costigliola <[email protected]>
> > To: J Programming Forum <[email protected]>
> > Cc:
> > Sent: Wednesday, August 27, 2014 4:11:51 PM
> > Subject: Re: [Jprogramming] Trampolining (was Adler-32)
> >
> > Pascal, you are right. I would say that it is "generally accepted" that
> in
> > J, power is the way to do iteration. I would bet very few people use $:
> > much given that (^:) and (/), (\) etc. can easily model most problems.
> But
> > for some people using recursion is more (or equally) instinctive. So,
> this
> > was merely an exercise on implementing a stack-less $: . That being
> said, I
> > think once tested and made robust, the speed boost and avoidance of the
> > function call stack will lead to some benefits of ($:) over (^:). One is
> > that it is, in my opinion, cleaner to implement algorithms that need to
> > stop early. Another is that wider adoption will hopefully lead to
> recursion
> > being added to the toolbox of "tools of thought" of J programmers.
> >
> > I am actually more encouraged now about the prospects of O. given your
> > examples, as the tail recursive version runs in roughly the same amount
> of
> > time and less space than the power version. Of course this is just one
> > simple example. Here are the timings on my computer:
> >
> > ts '50000 fibtac O. 0 1x'
> > 1.212615105792 84352
> >
> > ts 'fib 50000 0 1x'
> > 1.252843949962 233216
> >
> >
> >
> >
> > On Wed, Aug 27, 2014 at 3:39 PM, 'Pascal Jasmin' via Programming <
> > [email protected]> wrote:
> >
> > > also if you really wanted to call it dyadically,
> > >
> > > fib =: (<:X, {:Y , +/Y)Guard (0 < {.) Cleanup {: (@:,)
> > > or
> > > fib =: (<:X, {:Y , +/Y) Guard(0 < {.) Cleanup{: @:,
> > > 10 fib 0 1x
> > > 89
> > >
> > >
> > > ----- Original Message -----
> > > From: 'Pascal Jasmin' via Programming <[email protected]>
> > > To: "[email protected]" <[email protected]>
> > > Cc:
> > > Sent: Wednesday, August 27, 2014 3:28:35 PM
> > > Subject: Re: [Jprogramming] Trampolining (was Adler-32)
> > >
> > > The technique of placing all parameters on left hand side and using ^:
> is
> > > stackless
> > > X=.@{.
> > > Y
> > > =.@}.
> > >
> > > fib =: (<:X, {:Y , +/Y)Guard (0 < {.) Cleanup {: NB. using previous
> > > definitions, that aren't really necessary, as it gets compiled to:
> > >
> > > fib
> > > [: {: (<:@{. , {:@}. , +/@}.)^:(0 < {.)^:_
> > >
> > > but for clarity:
> > > Guard
> > > 2 : 'u ^:v^:_'
> > > Cleanup
> > > 2 : '[: v u'
> > >
> > >
> > > fib 10000 0 1x
> > > 544383731135652813387342609937503801353891845546959670262477158412...
> > >
> > > timespacex 'fib 10000 0 1x'
> > > 0.0630729 128896
> > > timespacex '1e4 fibtco 0 1x'
> > > 0.273644 42752
> > >
> > >
> > > Can't explain why it uses more mem though, though my machine is
> > apparently
> > > much slower than yours.
> > >
> > >
>
>
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
