From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Tim Van den Langenbergh Newsgroups: gmane.lisp.guile.user Subject: Re: Question about data structures Date: Sun, 22 Nov 2020 23:50:47 +0100 Message-ID: <4033601.nszuQzh3Xh@terra> References: Mime-Version: 1.0 Content-Type: multipart/signed; boundary="nextPart7419703.qp7NimKd59"; micalg="pgp-sha256"; protocol="application/pgp-signature" Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="5192"; mail-complaints-to="usenet@ciao.gmane.io" To: guile-user@gnu.org Original-X-From: guile-user-bounces+guile-user=m.gmane-mx.org@gnu.org Sun Nov 22 23:52:33 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 1kgyDh-0001GR-Jc for guile-user@m.gmane-mx.org; Sun, 22 Nov 2020 23:52:33 +0100 Original-Received: from localhost ([::1]:54374 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1kgyDg-0000UU-EP for guile-user@m.gmane-mx.org; Sun, 22 Nov 2020 17:52:32 -0500 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:38820) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1kgyCC-0008Ve-Iu for guile-user@gnu.org; Sun, 22 Nov 2020 17:51:00 -0500 Original-Received: from mout.gmx.net ([212.227.17.20]:54747) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1kgyCA-0005mL-4Y for guile-user@gnu.org; Sun, 22 Nov 2020 17:51:00 -0500 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=gmx.net; s=badeba3b8450; t=1606085454; bh=SsvYzemaTcKJyHsH33rMFJ2Cn39ztA1zlNkT9lquxlw=; h=X-UI-Sender-Class:From:To:Subject:Date:In-Reply-To:References; b=Mqs1POyscN+7tSa2DvNd22I1ujC5/ZC5AVaxzwFvNFbUtGSreWcQG7spmi5TSDrG5 SJU9QpT1w8JT8RwwVVhpN4yjm0VogJLq3WzviJe8hOwXzJrKN+Demc5QQ4dqVM4h9R 0HvtFpCm33/g9jOnZCY+JWt7LXE5sqgTRG5rS3DM= X-UI-Sender-Class: 01bb95c1-4bf8-414a-932a-4f6e2808ef9c Original-Received: from terra.localnet ([94.227.125.226]) by mail.gmx.com (mrgmx104 [212.227.17.174]) with ESMTPSA (Nemesis) id 1MCbIx-1kXrG11G3n-009eN2 for ; Sun, 22 Nov 2020 23:50:54 +0100 In-Reply-To: X-Provags-ID: V03:K1:UC+f1k8Bv5wXLgjM1qIXVYePrneJmxNY5gFcJgfxG/aBE2qB36k Q0+QqOj+ERWVsTLlZYsbaO5XCCArLsp5s+zg6EbPlLSBxmaKugqzmYofHRZd+OE5FVDVGH8 RFUBzrNBV0r9hHVauMlLDFvC1A8z3qTJl1HKfiRH0hMgDBP15Bu6qaTz5xwpVMEcWO+YpNg U1vAGm8kYfibAaRkrW0Nw== X-UI-Out-Filterresults: notjunk:1;V03:K0:HyLSmQd7z+E=:mCBxCipATK52VTBaDX/6FL 9YDYxYuuIZbRyfdRcPho4I2ZrFBQM+LrGDWfp/nB0Ukltbdv8/eNd2B/gmpPX6s6cEBxs4F// VHHHcC+0XKC0ClrEMBrgvZKbYJ5YrDODEq9LWf7aqnH3F8WFK3oXrgtNkzpvpFh/xpRkvuXcV LYve/tL54Dr5O4MI2nDfNsJOo9eJan8SysuB2HGFlBka5prNVp/Ne60WC1P/+3kP9n4Hk6/sr YHlCJQuBiIOTTie0qSnpGZOrWpxWo3C6bLD0bcqSgMLlFeejq5sA3FAmO3uLPwU4tHrcEvTjF lKpgvB3kfQSLY+j4hz2OrpiQCazbHYXxMfggMG6ia97/7xI2bDQIGPLDDLvL4JWAUaK+iL5lj 7veK5r0nQpA04WvJNk1UWo6jxKLy2genspQcW/JxtjxVUB6SW0LN/VI/3viIohy95Ee8Ea6x8 J3VdYqgKX30GTtpDqHSb3HuHbjfe+4w7Bjne0y1fn+FN+Chtdf82RUM9jsP9Aqw8m4hVarWDb /3Grgr/vtgjLZL3wF2+v/sN6uA4DOQnGCfYni6BklLMzZSRgEq7Lpj0prG1/9S05+7m8eWk8G eEwnmteYYczsePH4JIUmrgY/H0+ZIOlqO0GXod5ShaQVUL1telYnWhRuBXxcylIpg4nFYjATZ HmVjE0l0hJNQM9lvJn3IQQLA+jSzlwnvSW6x0F0CcoBvC5prX1Rc22GY7PYXIyJxl4YvBf6M5 ip3IJhK478wOOm7Rx7RksbCMHrWVLtJSj7oeOAD7jbs54/vE3AHgLY7wxVO8uwxWl/b4hW2I Received-SPF: pass client-ip=212.227.17.20; envelope-from=tmt_vdl@gmx.com; helo=mout.gmx.net X-Spam_score_int: -25 X-Spam_score: -2.6 X-Spam_bar: -- X-Spam_report: (-2.6 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, FREEMAIL_FROM=0.001, RCVD_IN_DNSWL_LOW=-0.7, RCVD_IN_MSPIKE_H2=-0.001, 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:17042 Archived-At: --nextPart7419703.qp7NimKd59 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="us-ascii"; protected-headers="v1" From: Tim Van den Langenbergh To: guile-user@gnu.org Subject: Re: Question about data structures Date: Sun, 22 Nov 2020 23:50:47 +0100 Message-ID: <4033601.nszuQzh3Xh@terra> In-Reply-To: References: On Sunday, 22 November 2020 19:48:24 CET Zelphir Kaltstahl wrote: > Hello Guile Users! > > I have a question about data structures. > > Recently I read a file and the lines in the file would become a list in > my Guile program. The file was not super big or anything. However, I > usually try to avoid having to use `append` or `reverse`, whenever > possible, considering, that they are O(n) operations and in principle I > do not want to write code, that uses lists in inefficient ways, when > there is a more efficient way. That said, I hit a little snag: > > When I am reading a file and do not know how many lines there are in the > file, I can use a normal list and construct it using recursive calls > like `(cons line (iter ...))` where `iter` is the recursive call and. > Could also be called `process-next-line` or simply `next`. Since I am > building a recursive data structure, it is OK to have a non-tail > position recursive call. Then I would return that list and work with it. > However, what if I ever need to add a list entry and the order of list > entry matters? I would either have to use `append`, to add it to the > end, which would be O(n), or I would have to initially construct the > list of lines in reversed order from initially, so that I can add by > simply using `(cons new-entry lines)`. However, when I use the list in > reverse and ever need to output the lines in the list in their original > order, I would first need to `reverse` the list again. > > OK the whole reversing would not be a problem, if I used a vector to > store the lines. However, then I would need to know the number of lines > in the file ahead of time or look at the file once for counting the > lines, then create the vector of that length and then store the lines in > it. This seems inelegant again, because I look at the lines of the file > twice. I could read it in as a list and then use `list->vector`, but > that will also be an additional O(n) for converting every entry to > vector element. > > If I now think about Python, then I have Python lists (actually arrays?) > and those can be easily appended to in O(1) and random access is also > O(1) according to https://wiki.python.org/moin/TimeComplexity. This > means I do not need to think much about how I will use the lines of a > file, when reading in the file. A Python list will be appropriate. > > So in Guile I sometimes feel some mental overhead of thinking about the > choice of data structure, which I do not feel in Python. Generally I > like Guile a lot more, so I would like to know how others deal with > this. Here are some ideas for it: > > 1. I could create some abstraction layer for the "sequence of read > lines", which I use inside the procedure, which reads in the lines and > all other code, that works with the lines, so that I can rather easily > later exchange the data structure. A data abstraction. However, that > might only hide the complexities of some operations behind the > abstraction and not reduce them. > > 2. Perhaps I want Guile's arrays? (Can they be expanded in O(1)? I do > seem to remember reading, that Guile vectors are only a special case of > Guile arrays, so that would mean they are not expandable in O(1).) > > 3. Just convert list to vector after reading in the file until I hit a > problem, where that additional O(n) really becomes a problem. (In my > current project it is not realistically a problem.) But this does not > satisfy me. I should learn how to solve the problem in general and use > the best way to do things. > > 4. Perhaps I need to write another data structure, that creates a new > vector, when the previous one is full, managing the expansion myself. > > How do you approach this problem? Is it a problem at all? > > Best regards, > Zelphir > > Hey Zelphir, If you want to use a FIFO data structure, you may want to check out queues= . They're already in ice-9, under (ice-9 q). Mandatory manual reference: https://www.gnu.org/software/guile/manual/html_node/Queues.html#Queues Alternatively, if you want constant-time random access you could try using Vlists, although they aren't thread-safe. https://www.gnu.org/software/guile/manual/html_node/VLists.html#VLists Finally you could implement either a doubly-linked list or array list type depending on your needs. If I understand your requirements correctly I would recommend queues. They= are easy to work with. Sincerely yours, - Tim --nextPart7419703.qp7NimKd59 Content-Type: application/pgp-signature; name="signature.asc" Content-Description: This is a digitally signed message part. Content-Transfer-Encoding: 7Bit -----BEGIN PGP SIGNATURE----- iQIzBAABCAAdFiEEoaHRUPlqTFTeZ4f99QrzKNnR5jUFAl+660cACgkQ9QrzKNnR 5jXQZw/9FD/kmq22/Om1LH0/WYB7OIwjPa2NpJ4Zgx4wO++rjz2OLaXPzL20c29U Xa+Z651rn6uUNKZYiOKUXIrDNhq0NZT48LbuNPg6vVZguws3yCY4UlX2d/Qk34b3 nJ4SxTVKA3wVP0dF808IJf0UgTHfT0NIifJZvYxjdgADlbEeWEoorVmcT88Gq3Nx lqy90u9hRl8gmiW5/eucZE1bXJLUeYYnGvh4wsTnbItxPEMRI4bxVw6mCgn2YJwB WkHMCl3szeh416C2JHfsAbRfTLKBNDvVRdzx/tqA7/nNNsIP+jU3ppPHbGNkyzHN K/VD5cq+hGQQ5q9+nlQ/PzSq6Nd44LuRrbiHzPv2KAjOrYbK8jo3vrl2bgdIwvTb CK7gs6x6DdnQcGXqLSns8S41gBd1sk1vHDbK/pEakJ5xCMEGReOTkGM8N6ICjUDH EZ4zx8yWLkxbF93HX3j8sZnGPwq8Jd0CqNaqJWEeMuhvVJPkPYMvg23sCW9HOPLH MvRr9aU099EwZ/TX0c5kl9yza2zrbwUsyGIbQMuOqRm/HPY4uEr6oZvtl69WgyGc kqzC1io17eNnNjGEFY19kPDiLXxIe6qY+iHoNoG8MAGvTqXXcV8k33R7rb5r/w4V kfJ7CTYKdaj6Gh7KyMazzaO0AaKlyhQi61x6KxmFMwHdbuIzRkU= =DHov -----END PGP SIGNATURE----- --nextPart7419703.qp7NimKd59--