home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / comp / lang / lisp / 2929 < prev    next >
Encoding:
Text File  |  1992-11-21  |  2.6 KB  |  72 lines
  1. Xref: sparky comp.lang.lisp:2929 comp.lang.lisp.mcl:1654
  2. Newsgroups: comp.lang.lisp,comp.lang.lisp.mcl
  3. Path: sparky!uunet!europa.asd.contel.com!darwin.sura.net!spool.mu.edu!agate!boulder!cambridge.apple.com!apple!voder!gatekeeper.nsc.com!psinntp!psinntp!sunic!aun.uninett.no!nuug!ifi.uio.no!si.no!fenrix.si.no!haltraet
  4. From: haltraet@monsun.si.no (Hallvard Tr{tteberg)
  5. Subject: remove
  6. Message-ID: <722395542.26555@news.Colorado.EDU>
  7. Lines: 55
  8. Sender: news
  9. Organization: Center for Industrial Research, Dept. of Knowledge Based Systems
  10. Distribution: co
  11. Date: 20 Nov 92 08:11:21 GMT
  12. Approved: news
  13. X-Note1: mail msgid was <HALTRAET.92Nov20091121@monsun.si.no>
  14. X-Note2: message-id generated by recnews
  15. Lines: 55
  16.  
  17. Hi, I'm profiling some code and found out that it's consing much more
  18. than it should. I found that the following is true of MCL 2.0:
  19.  
  20. (let ((a '(1 2 3))) (eq    a (remove 0 a))) => nil, while of course
  21. (let ((a '(1 2 3))) (equal a (remove 0 a))) => t
  22.  
  23. Remove conses up a new list even though it doesn't remove anything!
  24. It shouldn't be difficult to write one that kept the biggest unchanged
  25. tail of the original list, returning the whole unmodified list if it
  26. didn't contain the first argument. It only requires an eq-test on the
  27. result from a recursive call:
  28.  
  29. (defun faster-remove (elt list)
  30.   (if (atom list)
  31.     (values list)
  32.     (let* ((cons (cdr list))
  33.            (cons-result (faster-remove elt (cdr list))))
  34.       (if (eq (car list) elt)
  35.         (values cons-result)
  36.         (if (eq cons cons-result)
  37.           (values list)
  38.           (cons (car list) cons-result))))))
  39.  
  40. Time-ing shows a big difference:
  41.  
  42. (DOTIMES (A 1000) (DOTIMES (B 8) (FASTER-REMOVE B '(1 2 3 4 5 1 2 3 4
  43. 5)))) took 2421 milliseconds (2.421 seconds) to run.
  44. Of that, 117 milliseconds (0.117 seconds) were spent in The
  45. Cooperative Multitasking Experience.
  46.  240000 bytes of memory allocated.
  47. NIL
  48. ? 
  49. (DOTIMES (A 1000) (DOTIMES (B 8) (REMOVE B '(1 2 3 4 5 1 2 3 4 5))))
  50. took 6966 milliseconds (6.966 seconds) to run.
  51. Of that, 376 milliseconds (0.376 seconds) were spent in The
  52. Cooperative Multitasking Experience.
  53.  640000 bytes of memory allocated.
  54. NIL
  55.  
  56. I know my function isn't as general as remove since it only works on
  57. lists and doesn't take all those arguments. But I feel remove should
  58. be optimized for the simplest cases and also should try to cons as
  59. little as possible. As the results show, faster-remove (or should it
  60. be called low-consing-remove) is far better when it comes to consing.
  61.  
  62. --
  63. Hallvard Traetteberg
  64. Dept. of Knowledge Based Systems
  65. Center for Industrial Research
  66. Box 124 Blindern, 0314 Oslo 3
  67. NORWAY
  68.  
  69. Tlf: +47 2 45 29 83 or  +47 2 45 20 10
  70. Fax: +47 2 45 20 40
  71. Email: Hallvard.Tretteberg@si.no
  72.