From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: David Kastrup Newsgroups: gmane.emacs.devel Subject: Re: Adding rassq-delete-all to lisp/subr.el. Date: Tue, 19 Apr 2005 17:12:42 +0200 Message-ID: <851x967qc5.fsf@lola.goethe.zz> References: <87k6my7v56.fsf@xs4all.nl> NNTP-Posting-Host: main.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Trace: sea.gmane.org 1113925422 862 80.91.229.2 (19 Apr 2005 15:43:42 GMT) X-Complaints-To: usenet@sea.gmane.org NNTP-Posting-Date: Tue, 19 Apr 2005 15:43:42 +0000 (UTC) Cc: emacs-devel@gnu.org Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Tue Apr 19 17:43:40 2005 Return-path: Original-Received: from lists.gnu.org ([199.232.76.165]) by ciao.gmane.org with esmtp (Exim 4.43) id 1DNurp-0002gP-0T for ged-emacs-devel@m.gmane.org; Tue, 19 Apr 2005 17:42:25 +0200 Original-Received: from localhost ([127.0.0.1] helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1DNuw9-0003iJ-MG for ged-emacs-devel@m.gmane.org; Tue, 19 Apr 2005 11:46:53 -0400 Original-Received: from mailman by lists.gnu.org with tmda-scanned (Exim 4.43) id 1DNuvn-0003fx-OR for emacs-devel@gnu.org; Tue, 19 Apr 2005 11:46:31 -0400 Original-Received: from exim by lists.gnu.org with spam-scanned (Exim 4.43) id 1DNuvl-0003db-T3 for emacs-devel@gnu.org; Tue, 19 Apr 2005 11:46:31 -0400 Original-Received: from [199.232.76.173] (helo=monty-python.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1DNuvl-0005is-Qv for emacs-devel@gnu.org; Tue, 19 Apr 2005 11:46:29 -0400 Original-Received: from [151.189.21.42] (helo=mail-in-02.arcor-online.net) by monty-python.gnu.org with esmtp (TLS-1.0:DHE_RSA_3DES_EDE_CBC_SHA:24) (Exim 4.34) id 1DNuRO-0006oZ-I8 for emacs-devel@gnu.org; Tue, 19 Apr 2005 11:15:06 -0400 Original-Received: from lola.goethe.zz (i538791E3.versanet.de [83.135.145.227]) by mail-in-02.arcor-online.net (Postfix) with ESMTP id CD9EE135139; Tue, 19 Apr 2005 17:12:55 +0200 (CEST) Original-Received: by lola.goethe.zz (Postfix, from userid 1002) id 0FFB51C1E222; Tue, 19 Apr 2005 17:12:42 +0200 (CEST) Original-To: Lute Kamstra In-Reply-To: <87k6my7v56.fsf@xs4all.nl> (Lute Kamstra's message of "Tue, 19 Apr 2005 15:28:53 +0200") User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.0.50 (gnu/linux) 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:36111 X-Report-Spam: http://spam.gmane.org/gmane.emacs.devel:36111 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. And I am not too fond of quadratic complexity algorithms. 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)))))) 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. 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. -- David Kastrup, Kriemhildstr. 15, 44793 Bochum