home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / sci / math / symbolic / 2235 < prev    next >
Encoding:
Internet Message Format  |  1992-08-19  |  2.4 KB
  1. Path: sparky!uunet!cs.utexas.edu!sdd.hp.com!hplabs!ucbvax!UX1.CSO.UIUC.EDU!gaylord
  2. From: gaylord@UX1.CSO.UIUC.EDU
  3. Newsgroups: sci.math.symbolic
  4. Subject: translating the APL 'deal' function into M recursively, procedurally and
  5.  functionally - one-liners are faster
  6. Message-ID: <199208201030.AA04285@ux1.cso.uiuc.edu>
  7. Date: 20 Aug 92 10:30:31 GMT
  8. Sender: daemon@ucbvax.BERKELEY.EDU
  9. Lines: 64
  10.  
  11. on p.200 in nancy blachman's book, an exercise (#11.4) is given to
  12. translate the APL function 'deal' which randomly selects elements from a
  13. list without replacement into M. it is recommended to do this recursively.
  14.  
  15. from the manuscript of a text, another person has written the deal function
  16. in M both procedurally and as a recursive rewrite rule and found that the
  17. procedural program runs 4 times faster than the recursive program:
  18.  
  19. it seems to me that the deal function is an obviously candidate for a
  20. one-liner: here it is:
  21.  
  22. deal1[lis_List,n_Integer]
  23. :=Complement[lis,Nest[Delete[#,Random[Integer,{1,Length[#]}]]&,lis,n]]
  24.  
  25. -----------------------------------------------
  26.  
  27. to clarify what's going on here:
  28.  
  29. SeedRandom[0]
  30. deal1[Range[9],4]
  31. {2, 5, 6, 7}
  32.  
  33. we can look at the actual selection process using NestList
  34.  
  35. SeedRandom[0]
  36. NestList[Delete[#,Random[Integer,{1,Length[#]}]]&,Range[9],4]
  37. {{1, 2, 3, 4, 5, 6, 7, 8, 9}, {1, 2, 3, 4, 5, 6, 8, 9}, 
  38.  
  39.   {1, 2, 3, 4, 5, 8, 9}, {1, 2, 3, 4, 8, 9}, 
  40.  
  41.   {1, 3, 4, 8, 9}}
  42.  
  43. ---------------------------------------------
  44.  
  45. i ran timing test on the recursive program[deal3], the procedural
  46. program[deal2] and the one-liner program[deal1] with the following results
  47.  
  48. {Timing[deal1[Range[200],60];],
  49. Timing[deal2[Range[200],60];],
  50. Timing[deal3[Range[200],60];]}
  51. {{0.866667 Second, Null}, {1.01667 Second, Null}, {5.25 Second, Null}}
  52.  
  53.  
  54. $RecursionLimit = 1000;
  55.  
  56.  
  57. {Timing[deal1[Range[200],200];],
  58. Timing[deal2[Range[200],200];],
  59. Timing[deal3[Range[200],200];]}
  60. {{2.01667 Second, Null}, {2.78333 Second, Null}, {14.3667 Second, Null}}
  61.  
  62. i can't say that the recursive or the procedural programs (which i did not
  63. write) are the best programs that can be written in those styles but i do
  64. think that the speed of the one-liner confirms the general view that the
  65. more compact the M program and and more built-in M functions that are used,
  66. the faster the code will run. 
  67.  
  68. richard j. gaylord, university of illinois, gaylord@ux1.cso.uiuc.edu
  69.  
  70. "if you're not programming functionally, then you must be programming
  71. dysfunctionally"
  72.  
  73.  
  74.  
  75.