This completes the performance TCO comparison (for dyadic ! aka binomial
coefficients); the following code includes undefined utilities but the
fixed code shown for the verbs has a proper linear representation
JVERSION
Installer: j602a_win.exe
Engine: j701/2012-12-06/12:20/x
Library: 6.02.023
NB. Binomial...
u ( swap=. [: u (-^:([ < 2 * ])~ u ])Lambda ) NB. Swaping x by y-x if
necessary
-^:([ < 2 * ])~ u ]
rs=. 103!:0 NB. Recursion scope (adv)
( binomial=. (1:`(%~ * $:&:<:)@.(*@:[))rs swap ) NB. Classic
-^:([ < 2 * ])~ 1:`(%~ * $:&:<:)@.(*@:[) (103!:0) ]
NB. Take 0...
( 'kk nn aa'=. 3 From )
┌───┬───┬───┐
│0&{│1&{│2&{│
└───┴───┴───┘
( tail=. (<: o kk) , (<: o nn) , (kk %~ aa * nn) )
<:@:kk , <:@:nn , kk %~ aa * nn
( BinomialTailCore=. aa`($: o tail) @. (* o kk) )
aa`($:@:tail)@.(*@:kk)
( Binomial=. BinomialTailCore f.rs o ( 1 ,~ ,) swap)
-^:([ < 2 * ])~ 2&{`($:@:(<:@:(0&{) , <:@:(1&{) , 0&{ %~ 2&{ *
1&{))@.(*@:(0&{)) (103!:0)@:(1 ,~ ,) ]
NB. Tail recursive (fixed)
( BinomialTCO=. BinomialTailCore f.O. o ( 1 ,~ ,) swap)
-^:([ < 2 * ])~ 2&{`($:@:(<:@:(0&{) , <:@:(1&{) , 0&{ %~ 2&{ *
1&{))@.(*@:(0&{))O.@:(1 ,~ ,) ]
NB. Tail recursive optimized (fixed)
1000 st &> ' 7 binomial 11' ; ' 7 Binomial 11' ; ' 7
BinomialTCO 11'
┌──────────────────────┬────┬──────────┬─────────┐
│ 7 binomial 11│5376│1.20417e_5│0.0647363│
├──────────────────────┼────┼──────────┼─────────┤
│ 7 Binomial 11│4096│1.78004e_5│0.0729104│
├──────────────────────┼────┼──────────┼─────────┤
│ 7 BinomialTCO 11│3328│1.07456e_5│0.0357613│
└──────────────────────┴────┴──────────┴─────────┘
10 st &> '777x binomial 1111x' ; '777x Binomial 1111x' ; '777x
BinomialTCO 1111x'
┌──────────────────────┬──────┬──────────┬───────┐
│777x binomial 1111x│763264│0.00160169│1222.51│
├──────────────────────┼──────┼──────────┼───────┤
│777x Binomial 1111x│941696│0.0366376 │34501.5│
├──────────────────────┼──────┼──────────┼───────┤
│777x BinomialTCO 1111x│136448│0.0362441 │4945.43│
└──────────────────────┴──────┴──────────┴───────┘
777x (binomial -: Binomial ) 1111x
1
777x (binomial -: BinomialTCO) 1111x
1
The problem is that this attempt computes the product in reverse order
relative to the way that the recursive verb binomial does. So,
NB. Take 1...
( 'kk nn aa bb'=. 4 From )
┌───┬───┬───┬───┐
│0&{│1&{│2&{│3&{│
└───┴───┴───┴───┘
tail=. (>: o kk) , (>: o nn) , (kk %~ aa * nn) , bb
BinomialTailCore=. aa`($: o tail)@.(nn <: bb)
( Binomial=. {: o (BinomialTailCore f.rs) o ((<:x -~ ,) , (1 , ]))
swap)
-^:([ < 2 * ])~ {:@:(2&{`($:@:(>:@:(0&{) , >:@:(1&{) , (0&{ %~ 2&{ * 1&{) ,
3&{))@.(1&{ <: 3&{) (103!:0))@:((<:@:[ -~ ,) , 1 , ]) ]
NB. Tail recursive (fixed)
( BinomialTCO=. {: o (BinomialTailCore f.O.) o ((<:x -~ ,) , (1 , ]))
swap)
-^:([ < 2 * ])~ {:@:(2&{`($:@:(>:@:(0&{) , >:@:(1&{) , (0&{ %~ 2&{ * 1&{) ,
3&{))@.(1&{ <: 3&{)O.)@:((<:@:[ -~ ,) , 1 , ]) ]
NB. Tail recursive optimized (fixed)
1000 st &> ' 7 binomial 11' ; ' 7 Binomial 11' ; ' 7
BinomialTCO 11'
┌──────────────────────┬────┬──────────┬─────────┐
│ 7 binomial 11│5376│5.38686e_6│0.0289598│
├──────────────────────┼────┼──────────┼─────────┤
│ 7 Binomial 11│4096│1.29532e_5│0.0530562│
├──────────────────────┼────┼──────────┼─────────┤
│ 7 BinomialTCO 11│3456│1.3314e_5 │0.0460133│
└──────────────────────┴────┴──────────┴─────────┘
10 st &> '777x binomial 1111x' ; '777x Binomial 1111x' ; '777x
BinomialTCO 1111x'
┌──────────────────────┬──────┬──────────┬───────┐
│777x binomial 1111x│763264│0.00164413│1254.91│
├──────────────────────┼──────┼──────────┼───────┤
│777x Binomial 1111x│459008│0.00114213│524.247│
├──────────────────────┼──────┼──────────┼───────┤
│777x BinomialTCO 1111x│7808 │0.00117944│9.20908│
└──────────────────────┴──────┴──────────┴───────┘
777x (binomial -: Binomial ) 1111x
1
777x (binomial -: BinomialTCO) 1111x
1
Now, we can compare to other contenders,
stream=. }: o |. o ((i. o >:x) ([ ,. +) -~)
update=. 0 , {.x %~ {:x * {:y
( BinomialInsert=. {: o (update/) o stream f.swap )
-^:([ < 2 * ])~ {:@:((0 , {.@:[ %~ {:@:[ * {:@:])/)@:(}:@:|.@:(i.@:>:@:[ ([
,. +) -~)) ]
5 st &> '7777x ! 11111x' ; '7777x BinomialInsert 11111x'
; '7777x BinomialTCO 11111x'
┌───────────────────────────┬───────┬──────────┬───────┐
│7777x ! 11111x│4429056│0.00528417│23403.9│
├───────────────────────────┼───────┼──────────┼───────┤
│7777x BinomialInsert 11111x│1152000│0.0386458 │44520 │
├───────────────────────────┼───────┼──────────┼───────┤
│7777x BinomialTCO 11111x│29824 │0.0387387 │1155.34│
└───────────────────────────┴───────┴──────────┴───────┘
7777x (! -: BinomialInsert) 11111x
1
7777x (! -: BinomialTCO ) 11111x
1
For bigger numbers the magic behind the primitive (!) implementation really
shows up!
PS. Some xs appearing above are redundant but I like the way they look ;)
On Fri, Aug 29, 2014 at 3:56 PM, Jose Mario Quintana <
[email protected]> wrote:
>
> 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.
>
>
>
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
