From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: "Thompson, David" Newsgroups: gmane.lisp.guile.user Subject: Re: [EXT] Re: Question about data structures Date: Mon, 23 Nov 2020 09:54:35 -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="36841"; 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 15:56:30 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 1khDGX-0009Sp-RY for guile-user@m.gmane-mx.org; Mon, 23 Nov 2020 15:56:29 +0100 Original-Received: from localhost ([::1]:44100 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1khDGW-0006RV-Sb for guile-user@m.gmane-mx.org; Mon, 23 Nov 2020 09:56:28 -0500 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:45966) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1khDEw-0005Ex-JL for guile-user@gnu.org; Mon, 23 Nov 2020 09:54:50 -0500 Original-Received: from mail-ua1-x92b.google.com ([2607:f8b0:4864:20::92b]:33047) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1khDEu-0005Zs-Ca for guile-user@gnu.org; Mon, 23 Nov 2020 09:54:50 -0500 Original-Received: by mail-ua1-x92b.google.com with SMTP id r23so5747558uak.0 for ; Mon, 23 Nov 2020 06:54:47 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=worcester-edu.20150623.gappssmtp.com; s=20150623; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=Sks2s9nlshiLOUCKi9zADSgMw+o+d8Wq1+nLOGMpz/c=; b=LK7VnlEHAOuT+I4Kph8+lg9mD4oif9wflrVxLOgHbUkkp24DSSxiitqn/bgdUNUW56 WppugZjZTP7oP0CSrjrTgGqUYwECfLW+5V3GlQc+hoswTh290voH9XvPWlW+tf92294z qg4rAITekM2+f9vpFzUVD44Tfelbj81skmcfI2gztXyBKiIV+X9W+RB3wkxz/cxZlT7c L0Nkyyvb9LrXVmK+p54RdyT0OH2NatxwXJesYn+zNMphAAPg88yE15Hy2yXTUCOHreZ4 i1e3mQxmHNLNeKL/aRFIBZ9fHtKUDLqcWW/AzsegpZwFzgXAwLh3r9llyhjr4dPH2QEW 77sA== 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=Sks2s9nlshiLOUCKi9zADSgMw+o+d8Wq1+nLOGMpz/c=; b=eNr+3DDHkLuf7fmecBaaQ35gONbH0zkXJ6EXqKuNM2ORLwwy+nNIbk6LVnOslFF+tx 79HYKbHfgfJ3gAqMqOE1lQpqOc4zz6fd37K1Rr1Fs3XWubUkPuxH32lkaLjK+4L9QXrK X5gEnMEiXDWMyKBGp5h+P8C8SZyN6Zvpv5/5ijE6nKBgZL9G+ll0HXJLLfUvClTxvnbg AroNNc4P/IzAcrKXknQoVxHNqpolyAW77rbYJbu/00B0ct6gT2474evRlgqYHw44tpYd lrMt6zUq9OLAA66y0YrdVlNHqjIDi/oJFau6HIAlG/ptFqYCF09ZHheNxivS0xUCwYoV c/Rg== X-Gm-Message-State: AOAM533mVJfPkRto1MWRcq31WvpZd+N4DzfzIIUlMfG/2qWzwZ6x3KY5 aUxF7/SBSVrVa1gxhiuuQbRUKvpIvxNDRdHl3EXTVw== X-Google-Smtp-Source: ABdhPJyU4n6QlRVntFTucf48uHAfPw3XmweE7H44EoLEqS22PTou2BY1vzAgUxVAnSXBz1am7YYWL3cuM6/0Gcn9LXw= X-Received: by 2002:ab0:1606:: with SMTP id k6mr19477808uae.80.1606143286845; Mon, 23 Nov 2020 06:54:46 -0800 (PST) In-Reply-To: Received-SPF: pass client-ip=2607:f8b0:4864:20::92b; envelope-from=dthompson2@worcester.edu; helo=mail-ua1-x92b.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, 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-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:17049 Archived-At: On Sun, Nov 22, 2020 at 10:43 PM Taylan Kammer wrote: > > 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... > > Inserting an element at the beginning or middle is also relatively > expensive with those implementations, since all elements need to be > shifted forward to make space for the new element. (Although this might > be done with an operation like C's memcpy which is still actually very > fast.) > > It's called a "dynamic array" by Wikipedia: > > https://en.wikipedia.org/wiki/Dynamic_array > > If you want to go on an adventure, you could implement a Scheme data > structure called DVector that implements this strategy, using plain > Scheme vectors for the backing array. If anyone is interested in such a data structure, I have an implementation available here: https://git.dthompson.us/chickadee.git/tree/chickadee/array-list.scm I typically use them as object pools to reduce allocation and thus GC pressure in the context of video games. The array-list-push! and array-list-pop! procedures make it easy to use as a dynamically expanding stack. - Dave