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