From ... From: Erik Naggum Subject: Re: problem with delete Date: 2000/10/06 Message-ID: <3179815096735973@naggum.net>#1/1 X-Deja-AN: 678236502 References: <8r9vam$ie5$1@curofix.ida.liu.se> <3179481728635665@naggum.net> <3179724553025467@naggum.net> mail-copies-to: never Content-Type: text/plain; charset=us-ascii X-Complaints-To: newsmaster@eunet.no X-Trace: oslo-nntp.eunet.no 970828454 6420 195.0.192.66 (6 Oct 2000 10:34:14 GMT) Organization: Naggum Software; vox: +47 800 35477; gsm: +47 93 256 360; fax: +47 93 270 868; http://naggum.no; http://naggum.net User-Agent: Gnus/5.0803 (Gnus v5.8.3) Emacs/20.7 Mime-Version: 1.0 NNTP-Posting-Date: 6 Oct 2000 10:34:14 GMT Newsgroups: comp.lang.lisp * tar@sevak.isi.edu (Thomas A. Russ) | OK, here's the structure sharing remove for lists. I won't attempt it | for non-list sequences. The only nastiness is that anytime a copy needs | to be made, the copied part is traversed 3 times. (See ;; ***) The non-sharing remove only copies the not-to-be-removed elements, like, once: (defun normal-remove (item list) (loop for elt in list unless (eq item elt) collect elt)) Incidentally, since you're looking at sharing only some tail of the list, you could reverse the list, scan for the first match, reverse the part you had traversed, and copy the rest of the list, sans matches. This would avoid any but the final copy. A deeply recursive function could maintain a global variable that would allow it to share structure on the way back. All in all, I think the simplicity in implementation of a remove that copies is much to be preferred over the speed penalty for the version that tries to share. Another useful tidbit here is that if you're using a generational garbage collector, mixing and matching old and young generations usually has costs #:Erik -- If this is not what you expected, please alter your expectations.