From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: John Mastro Newsgroups: gmane.emacs.help Subject: Re: cl-dolist, dolist, cl-return, Date: Wed, 8 Jul 2015 18:49:34 -0700 Message-ID: References: <87fv4za4jo.fsf@nl106-137-147.student.uu.se> <87k2ub2bgb.fsf@nl106-137-147.student.uu.se> <87oajmi6eh.fsf@nl106-137-147.student.uu.se> NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=UTF-8 X-Trace: ger.gmane.org 1436406609 14661 80.91.229.3 (9 Jul 2015 01:50:09 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Thu, 9 Jul 2015 01:50:09 +0000 (UTC) To: "help-gnu-emacs@gnu.org" Original-X-From: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane.org@gnu.org Thu Jul 09 03:50:08 2015 Return-path: Envelope-to: geh-help-gnu-emacs@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1ZD0yW-00040x-OB for geh-help-gnu-emacs@m.gmane.org; Thu, 09 Jul 2015 03:50:08 +0200 Original-Received: from localhost ([::1]:37371 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1ZD0yW-0004gK-18 for geh-help-gnu-emacs@m.gmane.org; Wed, 08 Jul 2015 21:50:08 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:44411) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1ZD0yK-0004g6-Kc for help-gnu-emacs@gnu.org; Wed, 08 Jul 2015 21:49:57 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1ZD0yJ-0007Iv-Is for help-gnu-emacs@gnu.org; Wed, 08 Jul 2015 21:49:56 -0400 Original-Received: from mail-ob0-x22f.google.com ([2607:f8b0:4003:c01::22f]:35217) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1ZD0yJ-0007Hy-DO for help-gnu-emacs@gnu.org; Wed, 08 Jul 2015 21:49:55 -0400 Original-Received: by obbop1 with SMTP id op1so162743028obb.2 for ; Wed, 08 Jul 2015 18:49:53 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :content-type; bh=GFmWPuY2cYmy+ufq2DHVUrbzT5q/2nVle7O/RpaKZUg=; b=nlP9NgK2Mg1wiapy9g3fWq3xlEOVu6R0n9HvTMp6E/WB2I2jDGG6T1i29nzWWgmuJS FRiqS/k/TOIaqw17Dr3MpdYeFaiSkJie0Y2tQNwfDHepNn9hu6Xx/hncyzE1pl29Pg4Y auo5In2GIc6QhXI/45XtDb31W8DnvwwGtGgMHWNchedkdVsHLbhEn880B9lr0KuiKXkg mVKv4FdX/+MHoBQblkVpLD9FR5suYJRkmdGORDs3ZAXBkKCd/WGOdglstj70xBdguvAt 0pKtXnCmkMgTofbu8BzFHUqIVd8SHHW00lYk28d5uVYazCcl6DnwTKg6FKFAgSSzdded NdqA== X-Received: by 10.202.55.7 with SMTP id e7mr11694513oia.56.1436406593931; Wed, 08 Jul 2015 18:49:53 -0700 (PDT) Original-Received: by 10.76.168.70 with HTTP; Wed, 8 Jul 2015 18:49:34 -0700 (PDT) In-Reply-To: <87oajmi6eh.fsf@nl106-137-147.student.uu.se> X-detected-operating-system: by eggs.gnu.org: Error: Malformed IPv6 address (bad octet value). X-Received-From: 2607:f8b0:4003:c01::22f X-BeenThere: help-gnu-emacs@gnu.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: Users list for the GNU Emacs text editor List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane.org@gnu.org Original-Sender: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.help:105554 Archived-At: Emanuel Berg wrote: >> My point was that the re-evaluation part would be >> just a side-problem: even if your expression is >> a mere variable (so re-evaluating it is very cheap), >> the need to use `nth' at each step would force an >> O(N^2) complexity to this loop. > > You mean `nth' is linear, and `dotimes' is linear, so > the whole thing is linear**2 = quadratic? > > But I'm not using nth - probably you misread "neq". > (Ha! - maybe a reason not to do it just presented > itself...) > > Here is the code, which is linear, O(n), unless > there is a hidden nth somewhere... Stefan means that if, given `(dolist (x (list 1 2 3)) ...)', you evaluated `(list 1 2 3)' on every iteration you would end up doing something the moral equivalent of (setq elt (nth 0 (list 1 2 3))) ;; first iteration (setq elt (nth 1 (list 1 2 3))) ;; second iteration and so on, rather than (let ((the-list (list 1 2 3))) (setq elt (pop the-list)) ;; first iteration (setq elt (pop the-list))) ;; second iteration The latter case (which is how things really work) is obviously much more efficient, because the former case needlessly re-walks the list. -- john