From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: John Cowan Newsgroups: gmane.lisp.guile.user Subject: Re: Question about data structures Date: Sun, 22 Nov 2020 23:42:44 -0500 Message-ID: References: Mime-Version: 1.0 Content-Type: text/plain; charset="UTF-8" Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="38689"; mail-complaints-to="usenet@ciao.gmane.io" Cc: Guile User To: Taylan Kammer Original-X-From: guile-user-bounces+guile-user=m.gmane-mx.org@gnu.org Mon Nov 23 05:43:50 2020 Return-path: Envelope-to: guile-user@m.gmane-mx.org Original-Received: from lists.gnu.org ([209.51.188.17]) by ciao.gmane.io with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1kh3he-0009xT-DW for guile-user@m.gmane-mx.org; Mon, 23 Nov 2020 05:43:50 +0100 Original-Received: from localhost ([::1]:41462 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1kh3hd-0007Zu-FD for guile-user@m.gmane-mx.org; Sun, 22 Nov 2020 23:43:49 -0500 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:33214) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1kh3go-0006kd-PK for guile-user@gnu.org; Sun, 22 Nov 2020 23:42:58 -0500 Original-Received: from mail-qk1-x732.google.com ([2607:f8b0:4864:20::732]:38580) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1kh3gm-0007ts-AN for guile-user@gnu.org; Sun, 22 Nov 2020 23:42:58 -0500 Original-Received: by mail-qk1-x732.google.com with SMTP id i199so2474240qke.5 for ; Sun, 22 Nov 2020 20:42:55 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ccil-org.20150623.gappssmtp.com; s=20150623; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=elri18wcZg1+1v9uWcQpbYmGSQKnM0POA+ya0gglVfU=; b=IOmTJAasUN37CXxdlHgmU79cJWPWlovJV0o42fAlsvw0Obw+0mSNlFxhV/9pPbjDj0 YBzO0ghBqMHw3j3r4e5ETVOrnoIeDNPuACJVTstOCIWxmHWWyTK083nKzuD7Mk8eQQ8a auxv2/JD9Uoz51Rm9zhGLBv8uxKEyiD1F0/uQkFEAAW7FHccaHuv0TBfbnwNv+Vhq0Wh yruYNKFrRLoD+eY0KJl5Qxm5XxUaNLmvfTzW1+v8chXNzFxbaKz9csH8P36Y0yJSSTl/ 3TnHlduxO9oxvWwaIon6jrzenGVsO+BArcC3sOpioeF7FBOKEFm8e3ECJuMJph19xiPE aYxg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=elri18wcZg1+1v9uWcQpbYmGSQKnM0POA+ya0gglVfU=; b=otVN+vpt4XjK0Hjl0/g6QIxzJyNt3A2oSnvK5ZBCN4B6/lqU6GcbvgxtC5yarlZ0u4 fQHjS0ZFOTDz1448a0nuaVsUW9sZNbvohOD3MeI2DBwolvYu6iza8qicSu4Jl/rocaZn Rlw93FwovNbq6QgPP9IoduYmUBLF0Wp0mrfc5Mxq2RGmghNv4dnV6v82Nehf/us1cmTf pAmgIQbNVp0oxMbxEdzf2VPuDFxYcXL5O7qpk9wa2NUsxCOZYoXSH0ceuKM34MsKXgnO WkoBeAb1qUPRblV7SZhWF/wgVUmu8pOEqDLy0lfmL87a1+TKjoUHsOuMmmBKN8g9OTux FACw== X-Gm-Message-State: AOAM530tflJFWELe2Wdv5bPfU+IOk1GzZ3SsAMC2waGSGL1mmcG1O76X l73vby75JGsBmiyC3J1hsAOipkkV1pMB5Rtn9qaJaw== X-Google-Smtp-Source: ABdhPJwUx5prBIUOBe2Aa1AIF485A1Hp9tXADm9PqHCjnbpHTJnjeriXYzLl6sy/0maZRqQ940O/sl2/clO4AIxv1uw= X-Received: by 2002:ae9:c303:: with SMTP id n3mr28587526qkg.60.1606106575264; Sun, 22 Nov 2020 20:42:55 -0800 (PST) In-Reply-To: Received-SPF: pass client-ip=2607:f8b0:4864:20::732; envelope-from=cowan@ccil.org; helo=mail-qk1-x732.google.com X-Spam_score_int: -18 X-Spam_score: -1.9 X-Spam_bar: - X-Spam_report: (-1.9 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001 autolearn=ham autolearn_force=no X-Spam_action: no action X-Content-Filtered-By: Mailman/MimeDel 2.1.23 X-BeenThere: guile-user@gnu.org X-Mailman-Version: 2.1.23 Precedence: list List-Id: General Guile related discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: guile-user-bounces+guile-user=m.gmane-mx.org@gnu.org Original-Sender: "guile-user" Xref: news.gmane.io gmane.lisp.guile.user:17046 Archived-At: On Sun, Nov 22, 2020 at 10:43 PM Taylan Kammer wrote: Since your main concern seems to be appending, you could simply use a > linked list where you keep a reference to the last cons pair (tail) of > the list, so appending is simply a matter of a 'set-cdr!' operation on > the tail. > SRFI 117, List Queues, does exactly that. > Python lists, JDK's ArrayList, and .NET ArrayList, among probably many > other "list" or "array" data structures in popular languages nowadays > use a relatively straightforward data structure that is backed by an > actual array which can have empty slots (e.g. your Python list with 3 > elements might be backed by an array of size 10), and is reallocated > whenever there's no space left. This means that appending an element at > the end is usually dirt cheap, until there's no space left, at which > point the append operation is much heavier for one call, then the > following calls are dirt cheap again, until it's full again... > And the recent SRFI 214, Flexvectors, provides exactly this. Packaging these two SRFIs for Guile would be a Good Thing. John Cowan http://vrici.lojban.org/~cowan cowan@ccil.org The present impossibility of giving a scientific explanation is no proof that there is no scientific explanation. The unexplained is not to be identified with the unexplainable, and the strange and extraordinary nature of a fact is not a justification for attributing it to powers above nature. --The Catholic Encyclopedia, s.v. "telepathy" (1913)