From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: LanX Newsgroups: gmane.emacs.help Subject: Re: Reverse pop, return value Date: Tue, 17 Nov 2009 09:33:27 -0800 (PST) Organization: http://groups.google.com Message-ID: References: <87hbstm6sp.fsf@lola.goethe.zz> NNTP-Posting-Host: lo.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable X-Trace: ger.gmane.org 1258479769 19188 80.91.229.12 (17 Nov 2009 17:42:49 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Tue, 17 Nov 2009 17:42:49 +0000 (UTC) To: help-gnu-emacs@gnu.org Original-X-From: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane.org@gnu.org Tue Nov 17 18:42:42 2009 Return-path: Envelope-to: geh-help-gnu-emacs@m.gmane.org Original-Received: from lists.gnu.org ([199.232.76.165]) by lo.gmane.org with esmtp (Exim 4.50) id 1NAS4e-0000Wy-Hq for geh-help-gnu-emacs@m.gmane.org; Tue, 17 Nov 2009 18:42:40 +0100 Original-Received: from localhost ([127.0.0.1]:55043 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1NAS4e-0001QE-58 for geh-help-gnu-emacs@m.gmane.org; Tue, 17 Nov 2009 12:42:40 -0500 Original-Path: news.stanford.edu!usenet.stanford.edu!postnews.google.com!o10g2000yqa.googlegroups.com!not-for-mail Original-Newsgroups: gnu.emacs.help Original-Lines: 25 Original-NNTP-Posting-Host: 188.107.223.102 Original-X-Trace: posting.google.com 1258479208 19102 127.0.0.1 (17 Nov 2009 17:33:28 GMT) Original-X-Complaints-To: groups-abuse@google.com Original-NNTP-Posting-Date: Tue, 17 Nov 2009 17:33:28 +0000 (UTC) Complaints-To: groups-abuse@google.com Injection-Info: o10g2000yqa.googlegroups.com; posting-host=188.107.223.102; posting-account=W9fpQwoAAADZYmkl-8sXk1VPxG3rq-Pd User-Agent: G2/1.0 X-HTTP-UserAgent: Mozilla/5.0 (X11; U; Linux i686; de; rv:1.9.0.14) Gecko/2009090216 Ubuntu/8.10 (intrepid) Firefox/3.0.14, gzip(gfe), gzip(gfe) Original-Xref: news.stanford.edu gnu.emacs.help:174774 X-BeenThere: help-gnu-emacs@gnu.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Users list for the GNU Emacs text editor List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Original-Sender: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane.org@gnu.org Errors-To: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.help:69847 Archived-At: Hi On 17 Nov., 17:53, David Kastrup wrote: > Reversing is O(n), popping from the front O(1), so working off the whole > list is O(n). =A0Popping from the end is O(n), making work on the whole > list O(n^2). Thx David, good point! I will keep it in mind for cases where I can't control that lists are short. Anyway my motivation was more to learn basic things like (prog1)! Personally I prefer to delay optimizations (and potential complication of the code) to the point when profiling shows the need for it. But just from curiosity, having a FIFO stack situation (without clearly separated IN/OUT-phases where I can just reverse once) , whats the optimized way to push and pop then? Maybe always keeping a pointer to the end of the list? cheers Rolf