home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #31 / NN_1992_31.iso / spool / comp / lang / apl / 1269 < prev    next >
Encoding:
Text File  |  1992-12-27  |  1.8 KB  |  58 lines
  1. Newsgroups:   comp.lang.apl
  2. Path: sparky!uunet!gatech!rpi!utcsri!geac!itcyyz!yrloc!intern
  3. From:         eem@ipsaint.ipsa.reuter.COM (Mcdonnell, Eugene E.)
  4. Subject:      More efficient combinations verb
  5. Message-ID: <1992Dec27.212123.29935@yrloc.ipsa.reuter.COM>
  6. Sender: intern@yrloc.ipsa.reuter.COM (Intern via QUADRAM)
  7. Reply-To:     eem@ipsaint.ipsa.reuter.COM (Mcdonnell, Eugene E.)
  8. Organization: Reuters Information Services (Canada)
  9. Date:         27 Dec 92 21:00:03 UT
  10. Lines: 46
  11.  
  12.  
  13. -----------Message forwarded from IPSA Mailbox-------------
  14.  
  15.  
  16. no. 6857150 filed 20.45.47  sun 27 dec 1992
  17. from eem
  18. to   uclapl
  19. subj More efficient combinations verb
  20.  
  21. To Emmett McLean
  22.  
  23.  
  24.  Roger Hui has written a considerably more efficient version of
  25.  comb.  A comparison of timings on two cases:
  26.  
  27.  m  n   m comb n (McLean)  m comb n (Hui)  m comb1 n (Hui)
  28.  5 11         7.583333         0.166667       0.166667
  29.  6 12        89.18333          0.5            0.583333
  30.  
  31.  Hui's recursive comb is defined as follows:
  32.  
  33.     start =. i.@-.-
  34.     count =. <:@[ ! <:@[ + |.@start
  35.     index =. ;@:((i.-])&.>)
  36.     recur =. (count#start) ,. (index@count{comb&.<:)
  37.     test  =. *@[ *. <
  38.     basis =. i.@(<: , [)
  39.     comb  =. basis`recur @. test
  40.  
  41.  He points out that the recursion can be replaced by using power
  42.  (^:), and that m comb1 n is also grow^:m m seed n.  
  43.  
  44.     seed  =. *@[ i.@{ 1 0&,:@(,&1)@>:@(-~)
  45.     em    =. >:@{:@$
  46.     en    =. 2&+@{:@{:
  47.     g     =. em (count#start) en
  48.     h     =. em (index@count) en
  49.     grow  =. g ,. h { >:
  50.     comb1 =. [ grow@]^:(>{:@$) seed
  51.  
  52.  
  53. -----------------------------------------------------------
  54. This posting is forwarded from an internal Reuters mailbox.
  55. No statement or opinion contained herein should be taken as
  56. being Reuters policy, or even as being approved by Reuters,
  57. in any way.
  58.