home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / sci / math / symbolic / 2981 < prev    next >
Encoding:
Text File  |  1992-11-16  |  2.7 KB  |  97 lines
  1. Path: sparky!uunet!stanford.edu!agate!peoplesparc.Berkeley.EDU!fateman
  2. From: fateman@peoplesparc.Berkeley.EDU (Richard Fateman)
  3. Newsgroups: sci.math.symbolic
  4. Subject: Re: Rootterdam Competition in Mathematica Journal
  5. Date: 16 Nov 1992 19:39:52 GMT
  6. Organization: University of California, Berkeley
  7. Lines: 85
  8. Message-ID: <1e8te8INNaa3@agate.berkeley.edu>
  9. References: <BxtJGM.472@news.cso.uiuc.edu>
  10. NNTP-Posting-Host: peoplesparc.berkeley.edu
  11.  
  12.  
  13. I assume that mathematica competitions are not open to
  14. LISP solutions, but the split program is rather trivial in
  15. Common Lisp. 
  16. Here's the most obvious program ..
  17.  
  18.  
  19. ;;Rotterdam competition
  20.  
  21. #| requires (split '(a b c d e f g) '(2 0 3 1 1))  -->
  22.   ((a b) () (c d e) (f) (g))
  23. |#
  24.  
  25. (defun split (lis parts)
  26.   (if lis (cons (subseq lis 0 (car parts))
  27.          (split (nthcdr (car parts) lis)
  28.             (cdr parts)))))
  29.  
  30.  
  31. ;;.......
  32. For a problem resembling Richard Gaylord's,
  33. it seems that interpreted lisp on a Sparc1+ takes about 0.467
  34. sec and that compiled lisp takes about 0.017 seconds.  (Averaging it
  35. over 10 runs shows the latter number is probably somewhere in the
  36. range of 15-20 milliseconds.)
  37.  
  38. My conclusion:  lisp is neater for this task, it seems to be
  39. quite fast (a factor of 100, compiled? I don't know what machine
  40. Richard Gaylord was using).  Furthermore, I expect that any
  41. reasonably experienced lisp programmer would come to about the
  42. same solution, and would find it rather readable. 
  43.  
  44.  
  45. (for non-lispers, cdr=rest, car=first, cons= construct a list,
  46. subseq creates a list from a subsequence, nthcdr takes n cdrs.)
  47. .............
  48.  
  49. The testing code...
  50.  
  51.  
  52.  (setq r (make-array 500))
  53. #(NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL ...)
  54.  
  55. (dotimes (k 500)(setf (aref r k)(random 6)))
  56. NIL
  57.  
  58. (reduce #'+ r)
  59. 1312
  60.  
  61. (setf lis (coerce (make-array 1312) 'list))
  62. (NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL ...)
  63.  
  64. (setf r (coerce r 'list))
  65. (5 1 3 1 4 0 4 1 5 3 ...)
  66.  
  67. (time (split lis r))
  68. cpu time (non-gc) 467 msec user, 117 msec system
  69. cpu time (gc)     0 msec user, 0 msec system
  70. cpu time (total)  467 msec user, 117 msec system
  71. real time  700 msec
  72. space allocation:
  73.  10820 cons cells, 0 symbols, 68992 other bytes,
  74. ((NIL NIL NIL NIL NIL) (NIL) (NIL NIL NIL) (NIL) (NIL NIL NIL NIL) NIL
  75.  (NIL NIL NIL NIL) (NIL) (NIL NIL NIL NIL NIL) (NIL NIL NIL) ...)
  76.  
  77. (proclaim '(optimize speed (safety 0)))
  78. T
  79.  
  80. (compile 'split)
  81. SPLIT
  82. NIL
  83. NIL
  84.  
  85. (time (split lis r))
  86. cpu time (non-gc) 17 msec user, 0 msec system
  87. cpu time (gc)     0 msec user, 0 msec system
  88. cpu time (total)  17 msec user, 0 msec system
  89. real time  30 msec
  90. space allocation:
  91.  1814 cons cells, 0 symbols, 32 other bytes,
  92. ((NIL NIL NIL NIL NIL) (NIL) (NIL NIL NIL) (NIL) (NIL NIL NIL NIL) NIL
  93.  (NIL NIL NIL NIL) (NIL) (NIL NIL NIL NIL NIL) (NIL NIL NIL) ...)
  94. -- 
  95. Richard J. Fateman
  96. fateman@cs.berkeley.edu   510 642-1879
  97.