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: Thu, 21 Apr 2005 19:33:21 +0200 Message-ID: <871x948272.fsf@xs4all.nl> References: <87k6my7v56.fsf@xs4all.nl> <851x967qc5.fsf@lola.goethe.zz> <877jiy68hv.fsf@xs4all.nl> <854qe267rp.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 1114104771 14364 80.91.229.2 (21 Apr 2005 17:32:51 GMT) X-Complaints-To: usenet@sea.gmane.org NNTP-Posting-Date: Thu, 21 Apr 2005 17:32:51 +0000 (UTC) Cc: emacs-devel@gnu.org Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Thu Apr 21 19:32:49 2005 Return-path: Original-Received: from lists.gnu.org ([199.232.76.165]) by ciao.gmane.org with esmtp (Exim 4.43) id 1DOfX1-0007EK-DD for ged-emacs-devel@m.gmane.org; Thu, 21 Apr 2005 19:32:03 +0200 Original-Received: from localhost ([127.0.0.1] helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1DOfbl-00034y-QB for ged-emacs-devel@m.gmane.org; Thu, 21 Apr 2005 13:36:57 -0400 Original-Received: from mailman by lists.gnu.org with tmda-scanned (Exim 4.43) id 1DOfbW-00034Q-Ob for emacs-devel@gnu.org; Thu, 21 Apr 2005 13:36:42 -0400 Original-Received: from exim by lists.gnu.org with spam-scanned (Exim 4.43) id 1DOfbV-00033W-2V for emacs-devel@gnu.org; Thu, 21 Apr 2005 13:36:42 -0400 Original-Received: from [199.232.76.173] (helo=monty-python.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1DOfbU-0002zE-T5 for emacs-devel@gnu.org; Thu, 21 Apr 2005 13:36:41 -0400 Original-Received: from [194.109.24.30] (helo=smtp-vbr10.xs4all.nl) by monty-python.gnu.org with esmtp (Exim 4.34) id 1DOfaw-0003si-Dp; Thu, 21 Apr 2005 13:36:06 -0400 Original-Received: from pijl (a80-127-67-124.adsl.xs4all.nl [80.127.67.124]) by smtp-vbr10.xs4all.nl (8.12.11/8.12.11) with ESMTP id j3LHXMxP045992; Thu, 21 Apr 2005 19:33:22 +0200 (CEST) (envelope-from Lute.Kamstra@xs4all.nl) Original-Received: from lute by pijl with local (Exim 3.36 #1 (Debian)) id 1DOfYH-00019W-00; Thu, 21 Apr 2005 19:33:21 +0200 Original-To: David Kastrup In-Reply-To: <854qe267rp.fsf@lola.goethe.zz> (David Kastrup's message of "Tue, 19 Apr 2005 18:39:06 +0200") User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.0.50 (gnu/linux) Original-Lines: 41 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:36244 X-Report-Spam: http://spam.gmane.org/gmane.emacs.devel:36244 David Kastrup writes: > Lute Kamstra writes: > >> David Kastrup writes: >> >>> And I am not too fond of quadratic complexity algorithms. >> >> Me neither, but I was lazy and adapted assq-delete-all. >> >>> 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. > > Ah, right. If we removed all elements piecemeal, this would be > different. No, that would still run in linear time. To get quadratic behavior, you can do this: (defun checkit () (setq x nil) (dotimes (i 100000) (push '(a . a) x) (push '(b . b) x)) (float-time (time-since (prog1 (current-time) (rassq-delete-all 'a x))))) Lute.