From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Lute Kamstra Newsgroups: gmane.emacs.devel Subject: Re: Adding rassq-delete-all to lisp/subr.el. Date: Tue, 19 Apr 2005 18:23:24 +0200 Message-ID: <877jiy68hv.fsf@xs4all.nl> References: <87k6my7v56.fsf@xs4all.nl> <851x967qc5.fsf@lola.goethe.zz> NNTP-Posting-Host: main.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Trace: sea.gmane.org 1113928995 15246 80.91.229.2 (19 Apr 2005 16:43:15 GMT) X-Complaints-To: usenet@sea.gmane.org NNTP-Posting-Date: Tue, 19 Apr 2005 16:43:15 +0000 (UTC) Cc: emacs-devel@gnu.org Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Tue Apr 19 18:43:12 2005 Return-path: Original-Received: from lists.gnu.org ([199.232.76.165]) by ciao.gmane.org with esmtp (Exim 4.43) id 1DNvms-00057A-L2 for ged-emacs-devel@m.gmane.org; Tue, 19 Apr 2005 18:41:22 +0200 Original-Received: from localhost ([127.0.0.1] helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1DNvrD-0002HY-Q2 for ged-emacs-devel@m.gmane.org; Tue, 19 Apr 2005 12:45:51 -0400 Original-Received: from mailman by lists.gnu.org with tmda-scanned (Exim 4.43) id 1DNvqA-00024k-KT for emacs-devel@gnu.org; Tue, 19 Apr 2005 12:44:46 -0400 Original-Received: from exim by lists.gnu.org with spam-scanned (Exim 4.43) id 1DNvq8-00023o-E4 for emacs-devel@gnu.org; Tue, 19 Apr 2005 12:44:45 -0400 Original-Received: from [199.232.76.173] (helo=monty-python.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1DNvq8-0001n0-7C for emacs-devel@gnu.org; Tue, 19 Apr 2005 12:44:44 -0400 Original-Received: from [194.109.24.21] (helo=smtp-vbr1.xs4all.nl) by monty-python.gnu.org with esmtp (Exim 4.34) id 1DNvYC-0002ZQ-NY; Tue, 19 Apr 2005 12:26:13 -0400 Original-Received: from pijl (a80-127-67-124.adsl.xs4all.nl [80.127.67.124]) by smtp-vbr1.xs4all.nl (8.12.11/8.12.11) with ESMTP id j3JGNPqI075193; Tue, 19 Apr 2005 18:23:26 +0200 (CEST) (envelope-from Lute.Kamstra@xs4all.nl) Original-Received: from lute by pijl with local (Exim 3.36 #1 (Debian)) id 1DNvVV-0007OL-00; Tue, 19 Apr 2005 18:23:25 +0200 Original-To: David Kastrup In-Reply-To: <851x967qc5.fsf@lola.goethe.zz> (David Kastrup's message of "Tue, 19 Apr 2005 17:12:42 +0200") User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.0.50 (gnu/linux) Original-Lines: 84 X-Virus-Scanned: by XS4ALL Virus Scanner X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Original-Sender: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.devel:36114 X-Report-Spam: http://spam.gmane.org/gmane.emacs.devel:36114 David Kastrup writes: > Lute Kamstra writes: > >> lisp/subr.el currently defines assq-delete-all. What about providing >> rassq-delete-all as well? >> >> Lute. >> >> >> (defun rassq-delete-all (value alist) >> "Delete from ALIST all elements whose cdr is `eq' to VALUE. >> Return the modified alist. >> Elements of ALIST that are not conses are ignored." >> (let ((tail alist)) >> (while tail >> (when (and (consp (car tail)) (eq (cadr tail) value)) >> (setq alist (delq (car tail) alist))) >> (setq tail (cdr tail))) >> alist)) > > That is not what the function does. You are confusing cadr and cdar. Yup, I noticed. > And I am not too fond of quadratic complexity algorithms. Me neither, but I was lazy and adapted assq-delete-all. > It would seem much better to write > > (defun rassq-delete-all (value alist) > "Delete from ALIST all elements whose cdr is `eq' to VALUE. > Return the modified alist. > Elements of ALIST that are not conses are ignored." > (while (and (consp (car alist)) (eq (cdr (car alist)) value)) > (setq alist (cdr alist))) > (prog1 alist > (let ((tail alist)) > (while (setq tail (cdr tail)) > (if (and (consp (car tail)) > (eq (cdr (car tail)) value)) > (setcdr alist (cdr tail)) > (setq alist tail)))))) Nice. I find this rewrite a bit easier to understand, though: (defun rassq-delete-all (value alist) "Delete from ALIST all elements whose cdr is `eq' to VALUE. Return the modified alist. Elements of ALIST that are not conses are ignored." (while (and (consp (car alist)) (eq (cdr (car alist)) value)) (setq alist (cdr alist))) (let ((tail alist) tail-cdr) (while (setq tail-cdr (cdr tail)) (if (and (consp (car tail-cdr)) (eq (cdr (car tail-cdr)) value)) (setcdr tail (cdr tail-cdr)) (setq tail tail-cdr)))) alist) > If one takes > (defun checkit () > (setq x nil) > (dotimes (i 100001) (push (cons (- i) i) x)) > (float-time > (time-since (prog1 (current-time) > (dotimes (i 101) > (setq x (rassq-delete-all (* 100 i) x))))))) > > The discrepancy seems pretty small after byte compilation, which seems > strange. delq in defined in C and it's only called 101 times. > What makes a _significant_ difference is using (car (cdr...)) instead > of (cadr...): for some unfathomable reason, cadr introduces a > temporary binding to "x", and that is really expensive in the inner > loop. Strange, (cadr ...) is just a defsubst for (car (cdr ...)). So compiled it should make no difference. Lute.