Path: utzoo!utgpu!water!watmath!clyde!rutgers!husc6!think!barmar
From: barmar@think.COM (Barry Margolin)
Newsgroups: comp.lang.lisp
Subject: Re: Filtering Vectors in CL Question
Message-ID: <15622@think.UUCP>
Date: 27 Jan 88 22:04:53 GMT
References: <1350001@otter.HP.COM> <1350003@otter.HP.COM>
Sender: usenet@think.UUCP
Reply-To: barmar@sauron.think.com.UUCP (Barry Margolin)
Organization: Thinking Machines Corporation, Cambridge, MA
Lines: 50

In article <1350003@otter.HP.COM> kers@otter.HP.COM (Christopher Dollin) writes:
>So suppose someone says "please implement 'remove-if-not'. I would like
>your solution to generate no garbage if possible and to be reasonably
>efficient".

Here's a version I threw together quickly (note that it doesn't take
any options as the CL version does, and it only accepts a list, not
any sequence):

(defun simple-remove-if-not (test list)
  (let ((result nil))
    (dolist (item list)
      (unless (funcall test item)
	(push item result)))
    (nreverse result)))

The only inefficiency here is the NREVERSE at the end.  In Symbolics
Lisp I would use (LOOP ... COLLECT ...) because I know it uses a more
efficient collection mechanism involving maintaining a pointer to the
last cons in the result list; a portable version generates one garbage
cons cell (the Symbolics version uses a locative pointer to a local
variable):

(defun not-quite-so-simple-remove-if-not (test list)
  (let* ((result (ncons nil))
	 (current result))
    (dolist (item list)
      (unless (funcall test item)
	(rplacd current
		(setq current (ncons item)))))
    (cdr result)))

And here's one that doesn't generate any garbage but has a slightly
slower inner loop:

(defun even-less-simple-remove-if-not (test list)
  (let* ((result nil)
	 (current result))
    (dolist (item list)
      (unless (funcall test item)
	(if current
	    (rplacd current
		    (setq current (ncons item)))
	  (setq current (setq result (ncons item))))))
    result))
Barry Margolin
Thinking Machines Corp.

barmar@think.com
uunet!think!barmar