The main point about combM is that the use of M. makes some straightforward definitions of recursion functions competitive in efficiency.
combM=: 4 : 0 M. NB. All size x combinations of i.y if. (x>:y)+.0=x do. i.(x<:y),x else. (0,.x combM&.<: y),1+x combM y-1 end. ) I remember that this is very similar to the definition (sans M. of course) presented in Gilman & Rose, APL: An Interactive Approach. It is short and easy to understand, but performs poorly because of the double recursion. With the use of M. its execution time is within a factor of two of the highly optimized comb2. ----- Original Message ----- From: "R.E. Boss" <[EMAIL PROTECTED]> Date: Thursday, October 18, 2007 9:59 Subject: RE: [Jprogramming] Some consequences of M. To: 'Programming forum' <[email protected]> > Corrections on earlier figures. > > et=: 6!:2 > > load ... > et'facM 2000x' > 0.037963202 > 5 et'! 2000x' > 0.014093615 > > so almost 3 times as slow and, see below, a lot more space is used. > > > load .... > et'3 antibsM 10' > 0.014724162 > 5 et'3 #.^:_1 y'[y=.i.3^10 > 0.028449435 > > well, here the memoized verb is twice as fast, but also uses > twice the > space. > > load .... > et'antibsM 20' > 0.83372198 > 5 et'#: y'[y=.i.2^20 > 0.05074746 > > slower by a factor of 16 and 3 times more space. > > > et'10 combM 20' > 0.09148242 > 5 et'10 (comb2 i.) 20' > 0.048256231 > > almost twice as slow and more than twice as much space. > > > R.E. Boss > > > > -----Oorspronkelijk bericht----- > > Van: [EMAIL PROTECTED] [mailto:programming- > > [EMAIL PROTECTED] Namens Roger Hui > > Verzonden: donderdag 18 oktober 2007 16:40 > > Aan: Programming forum > > Onderwerp: Re: [Jprogramming] Some consequences of M. > > > > What you think are first calls may not be, depending on > > the definition of ts. With the timings you've given > > (e.g.3.327e_5 for 10 combM 20) I strongly suspect > > that space is executed first and the result cached, > > whence when time is executed it just got the result > > from the cache. See: > > http://www.jsoftware.com/pipermail/programming/2007- > October/008255.html> > > Unless, of course, you think that this kind of time > > comparison is meaningful. (I do not.) > > > > > > > > ----- Original Message ----- > > From: "R.E. Boss" <[EMAIL PROTECTED]> > > Date: Thursday, October 18, 2007 3:35 > > Subject: [Jprogramming] Some consequences of M. > > To: 'Programming forum' <[email protected]> > > > > > NB. all calls to memoized(?) verbs are first calls after > > > loading. Subsequent > > > calls are even more efficient. > > > > > > =================== > > > 0. recursion with M. can be faster than a primitive. > > > ------------------- > > > facM=:1:`(] * $:@<:)@.* M. > > > NB. \system\extras\help\dictionary\d212.htm > > > > > > 5 ts'! 2000x' > > > 0.013499039 179136 > > > ts'facM 2000x' > > > 0.00063421529 8479616 > > > (! -: facM) 2000x > > > 1 > > > '0.2,5.1,6.3' (8!:2) (,~*/)0.013499039 > 179136 % > > > 0.00063421529 8479616 > > > 0.45 21.3 0.021 > > > NB. relative performance, rel. execution time and rel. > ex. space. > > > > > > =================== > > > 1. you could have your own special code. > > > ------------------- > > > antibsM=: 3 : 0 M. NB. equivalent to x #.^:_1 i.x^y or (y#x) > #: i.x^y > > > 2 antibsM y > > > : > > > ix=.i.x > > > if. y=1 do. ,.ix > > > else. ,/ ix,"1"0 _ x antibsM <:y > > > end. > > > ) > > > > > > 5 ts'3 #.^:_1 y'[y=.i.3^10 > > > 0.02847991 4201536 > > > ts'3 antibsM 10' > > > 2.1428313e_5 9812096 > > > (3 #.^:_1 i.3^10) -: 3 antibsM 10 > > > 1 > > > '0.0,5.0,5.2' (8!:2) (,~*/)0.02847991 > 4201536 % > > > 2.1428313e_5 9812096 > > > 569 1329 0.43 > > > > > > 5 ts'#: y'[y=.i.2^20 > > > 0.047805544 33555008 > > > ts'antibsM 20' > > > 2.3639982e_5 1.1639277e8 > > > (#:i.2^20) -: antibsM 20 > > > 1 > > > '0,5.0,5.2'(8!:2) (,~*/)0.047805544 > 33555008 % > > > 2.3639982e_5 1.1639277e8 > > > 583 2022 0.29 > > > NB. relative performance, rel. execution time and rel. > ex. space. > > > > > > =================== > > > 2. (a lot of) performance records should be reconsidered. > > > ------------------- > > > NB. \system\extras\help\dictionary\dmcapdot.htm > > > combM=: 4 : 0 M. NB. All size x combinations of i.y > > > if. (x>:y)+.0=x do. i.(x<:y),x else. (0,.x combM&.<: > > > y),1+x combM y-1 end. > > > ) > > > > > > NB. http://www.jsoftware.com/jwiki/Essays/Combinations > > > comb2=: 4 : > > > > 0 NB. All size x combinations of y > > > d=. x-~#y > > > k=. |.(>:d),\y > > > z=. (d$<i.0 0),<i.1 0 > > > for_j. k do. z=. j ,.&.> ,&.>/\. z end. > > > ; z > > > ) > > > > > > 5 ts'10 (comb2 i.) 20' > > > 0.047006717 20793088 > > > ts'10 combM 20' > > > 3.3272275e_5 44555136 > > > 10 (combM -: (comb2 i.)) 20 > > > 1 > > > '0,5.0,5.2'(8!:2) (,~*/)0.053603614 > 20793088 % > > > 3.3272275e_5 44555136 > > > 752 1611 0.47 > > > NB. relative performance, rel. execution time and rel. > ex. space. ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
