sum3, tsum4, and tsum5 make assumptions that are invalid in more general cases. e.g.
p=: 0 2 5 4 0 0 4 ] v=: p: i.7 2 3 5 7 11 13 17 v tsum3 p 67 3 8 7 35 24 17 v tsum4 p 25 86 18 35 26 3 17 v tsum5 p 53 49 29 31 11 13 17 The verbs in http://www.jsoftware.com/jwiki/Essays/Tree_Sum do not have these defects. v tsum_mat p 58 3 8 7 35 21 17 v tsum_des p 58 3 8 7 35 21 17 v tsum_dfs p 58 3 8 7 35 21 17 ----- Original Message ----- From: "R.E. Boss" <[EMAIL PROTECTED]> Date: Friday, March 14, 2008 13:07 Subject: RE: [Jprogramming] tree sum and difference To: 'Programming forum' <[email protected]> > tsum4=:4 : '>{:trsm^:(a:~:{.)^:_ x;~}.&.|:(,:[EMAIL PROTECTED])y' > > trsm=: 3 : 0 > 'y0 y1'=. y > e=.((e.#]),:~[{~]i.e.#[)/ y0 > w=.(y1((([,-.~)[EMAIL PROTECTED]){])~ ~.{.y0)+(#y1){. ({.y0)+//.y1{~{:y0 > e;w > ) > > This evolved to > > tsum5=: 4 : '>{.trsm1^:(a:~:{:)^:_ x;}.y' > > trsm1=: 3 : 0 > 'y0 y1'=.y > z=.y0((-&#)[EMAIL PROTECTED]@])y1 > (y0+/@,: y1+//.y0{~z) ; y1([{~]i.e.#[) z > ) > > NB. tsum3 from > http://www.jsoftware.com/pipermail/programming/2008-March/010070.html > > > Some performance results. > > n4 =: 2e4 [EMAIL PROTECTED] 25 > p4 =: p: inv 1+i.2e4 > > n4 (tsum3 -:tsum4) p4 > 1 > n4 (tsum3 -:tsum5) p4 > 1 > > NB. ts=: 6!:2 , 7!:[EMAIL PROTECTED] > NB. scores=: 5 ts&> ] > > scores 'n4 tsum3 p4';'n4 tsum4 p4';'n4 tsum5 p4' > 0.016517373 1671104 > 0.010196401 2482368 > 0.0053659542 1695296 > > Relative performance: > > dspl rnkng scores 'n4 tsum3 p4';'n4 tsum4 p4';'n4 > tsum5 p4' > +-----+-----+-----+----+----+ > |verb |place|rlprf|rlt |rls | > +-----+-----+-----+----+----+ > |tsum3| 2 |3.23 |3.31|1.00| > +-----+-----+-----+----+----+ > |tsum4| 1 |2.42 |1.75|1.42| > +-----+-----+-----+----+----+ > |tsum5| 0 |1.00 |1.00|1.02| > +-----+-----+-----+----+----+ > > m=: _1+2^20 > n20=: m [EMAIL PROTECTED] 20 > p20a=: p: inv >: i.m > p20b=: 0,2#i.<.-:m NB. complete binary tree > > n20 (tsum3 -:tsum4) p20a > 1 > n20 (tsum3 -:tsum5) p20a > 1 > > scores 'n20 tsum3 p20a';'n20 tsum4 p20a';'n20 tsum5 p20a' > 1.2801371 94034560 > 1.1564694 1.300336e8 > 0.59123502 96477632 > > dspl rnkng scores 'n20 tsum3 p20a';'n20 tsum4 > p20a';'n20 tsum5 p20a' > +-----+-----+-----+----+----+ > |verb |place|rlprf|rlt |rls | > +-----+-----+-----+----+----+ > |tsum3| 1 |2.10 |2.15|1.00| > +-----+-----+-----+----+----+ > |tsum4| 2 |3.05 |1.95|1.60| > +-----+-----+-----+----+----+ > |tsum5| 0 |1.00 |1.00|1.03| > +-----+-----+-----+----+----+ > > n20 (tsum3 -:tsum4) p20b > 1 > n20 (tsum3 -:tsum5) p20b > 1 > > scores 'n20 tsum3 p20b';'n20 tsum4 p20b';'n20 tsum5 p20b' > 4.6031481 1.6362957e8 > 1.6110058 1.3842061e8 > 0.94681087 1.0067123e8 > > dspl rnkng scores 'n20 tsum3 p20b';'n20 tsum4 > p20b';'n20 tsum5 p20b' > +-----+-----+-----+----+----+ > |verb |place|rlprf|rlt |rls | > +-----+-----+-----+----+----+ > |tsum3| 2 |7.58 |4.86|1.56| > +-----+-----+-----+----+----+ > |tsum4| 1 |2.24 |1.70|1.32| > +-----+-----+-----+----+----+ > |tsum5| 0 |1.00 |1.00|1.00| > +-----+-----+-----+----+----+ > > > p4x=:0,}:i.#n4 NB. extreme case > > n4 (tsum3 -:tsum5) p4x > 1 > n4 (tsum3 -:tsum4) p4x > 1 > > scores 'n4 tsum3 p4x';'n4 tsum4 p4x';'n4 tsum5 p4x' > 0.52918958 4612864 > 0.091789114 5251456 > 0.073304202 3546880 > > dspl rnkng scores 'n4 tsum3 p4x';'n4 tsum4 p4x';'n4 > tsum5 p4x' > +-----+-----+-----+----+----+ > |verb |place|rlprf|rlt |rls | > +-----+-----+-----+----+----+ > |tsum3| 2 |8.71 |6.94|1.25| > +-----+-----+-----+----+----+ > |tsum4| 1 |1.78 |1.22|1.46| > +-----+-----+-----+----+----+ > |tsum5| 0 |1.00 |1.00|1.00| > +-----+-----+-----+----+----+ > > > R.E. Boss ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
