From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!.POSTED!not-for-mail From: Yuri Khan Newsgroups: gmane.emacs.help Subject: Re: beginnerquestion (nconc) Date: Fri, 17 Mar 2017 21:42:37 +0700 Message-ID: References: <87shmc1m2u.fsf@mail.de> NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable X-Trace: blaine.gmane.org 1489765846 26856 195.159.176.226 (17 Mar 2017 15:50:46 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Fri, 17 Mar 2017 15:50:46 +0000 (UTC) Cc: "help-gnu-emacs@gnu.org" To: Stefan Huchler Original-X-From: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane.org@gnu.org Fri Mar 17 16:50:42 2017 Return-path: Envelope-to: geh-help-gnu-emacs@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by blaine.gmane.org with esmtp (Exim 4.84_2) (envelope-from ) id 1cou9J-0006Ux-TQ for geh-help-gnu-emacs@m.gmane.org; Fri, 17 Mar 2017 16:50:42 +0100 Original-Received: from localhost ([::1]:49563 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1cou9P-0005Nn-PI for geh-help-gnu-emacs@m.gmane.org; Fri, 17 Mar 2017 11:50:47 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:49228) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1cot5o-0002ki-Cv for help-gnu-emacs@gnu.org; Fri, 17 Mar 2017 10:43:01 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1cot5n-0007xv-Hm for help-gnu-emacs@gnu.org; Fri, 17 Mar 2017 10:43:00 -0400 Original-Received: from mail-wr0-x232.google.com ([2a00:1450:400c:c0c::232]:35982) by eggs.gnu.org with esmtps (TLS1.0:RSA_AES_128_CBC_SHA1:16) (Exim 4.71) (envelope-from ) id 1cot5n-0007xm-BU for help-gnu-emacs@gnu.org; Fri, 17 Mar 2017 10:42:59 -0400 Original-Received: by mail-wr0-x232.google.com with SMTP id u108so53388967wrb.3 for ; Fri, 17 Mar 2017 07:42:59 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:sender:in-reply-to:references:from:date:message-id :subject:to:cc:content-transfer-encoding; bh=ZkAX87snt6eNOUP+G/zZo3InKpfaPwkw3gqel/RhrgI=; b=i0p2BdKV14AG5PKVNRjiXEOI9r0QVa9ZZAhFC16dJ2CEZAtzUglSI+PKdvyT55lLud n2xAz1KxWFyPUT/z/M1Y5DwVAvzhLG+rE2Y9YPrUQ4kUIWAXTlHjbVmwbCc2JaJvKkNx RyrGr3QE5XadRcIW8waUp7bfWE7UGwBDfXKqTpBrN6X2bg3nKYgiU6JTppGhmUVtH6Av iJWjEXcjjKBuajGeZDWxXT97F1aUz/Y4uh5Qo/XU4dYY38cYV2nHmgPXNouk5vVwj5OB YUDi5N2QoivdDigHr7U3swiX9Zm4AIleKtb9xbkK2GPx8CR8MoLrHm8mpmBKeTIq/Mb5 L71A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:sender:in-reply-to:references:from :date:message-id:subject:to:cc:content-transfer-encoding; bh=ZkAX87snt6eNOUP+G/zZo3InKpfaPwkw3gqel/RhrgI=; b=gmvOca70ntPW8c+xFhbIpM9ngimrkGrVMOPdTIdyB2bDWSa6tG/xcXVz6YI7QV9EEW NOq7x+pNk5I3Mc9YIJEZPNF6qLlW4H/umyHS8k/tQ1Sae1zLiO4bXJTI555Fi1IqWJV3 CyL6wUWJSQse+sQX7ntCxWSdd+4gOxEvJ0acvN6Fjov04mNcR6YjRAL0UmtxXqZqvuGV xsUmyc5yWrv/UeHbpm5PIn5AyAAJWzlwS+KpoDtSqfltcf5h3fjTccCy2uSUI1uiqX2v 6VKqWCu7rZ+yAC1lvTEIUNobdBQUml7aKgvefZC/GmaUSU2P6PJUrsVNSWbX6EQF1mhr mjcw== X-Gm-Message-State: AFeK/H3EWu9W2Iex/5LHlfKlFQWf2rMeDLK8q6graIhtuibm+qYQ7kfjd5oVVPHxVP7Jqx5i+4sfGyMrplimBQ== X-Received: by 10.223.152.239 with SMTP id w102mr14268461wrb.72.1489761778174; Fri, 17 Mar 2017 07:42:58 -0700 (PDT) Original-Received: by 10.223.142.141 with HTTP; Fri, 17 Mar 2017 07:42:37 -0700 (PDT) In-Reply-To: <87shmc1m2u.fsf@mail.de> X-Google-Sender-Auth: MlLo1jj1ihqruRESWvnLDAJPcwE X-detected-operating-system: by eggs.gnu.org: Genre and OS details not recognized. X-Received-From: 2a00:1450:400c:c0c::232 X-Mailman-Approved-At: Fri, 17 Mar 2017 11:49:59 -0400 X-BeenThere: help-gnu-emacs@gnu.org X-Mailman-Version: 2.1.21 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" Xref: news.gmane.org gmane.emacs.help:112591 Archived-At: On Fri, Mar 17, 2017 at 12:58 PM, Stefan Huchler w= rote: > I am a bit anoyed by push and reverse lists its not very straightforward > solution to create lists in loops, I found in the doku the nconc macro, > which looks like some sort of push that puts sequences at the end > instead of the beginning. You are probably annoyed because you are familiar with list implementations in other languages where appending an element is a cheap operation. For example, with a doubly linked list, appending at either end is constant time. However, Lisp uses singly linked lists. Appending at the start is a matter of allocating a single cons cell and setting its cdr to point to the old head of the list. However, appending at the end requires traversing the whole list to find its last cell, and then adding a new cell there. That=E2=80=99s what nconc does. So if your list is 1000 items long, populating it from beginning to end takes roughly 500000 operations. Populating from the end to beginning and then reversing will only take on the order of 3000 operations. Also, the empty list is a special case. It is represented as nil and does not *have* a last cell that nconc could modify. That=E2=80=99s why nco= nc does not work on the empty list.