From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Zelphir Kaltstahl Newsgroups: gmane.lisp.guile.user Subject: Question about data structures Date: Sun, 22 Nov 2020 19:48:24 +0100 Message-ID: Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 7bit Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="20513"; mail-complaints-to="usenet@ciao.gmane.io" User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:68.0) Gecko/20100101 Icedove/68.10.0 To: Guile User Original-X-From: guile-user-bounces+guile-user=m.gmane-mx.org@gnu.org Sun Nov 22 19:48:42 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 1kguPh-0005En-Q4 for guile-user@m.gmane-mx.org; Sun, 22 Nov 2020 19:48:41 +0100 Original-Received: from localhost ([::1]:50242 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1kguPg-0002Zt-RS for guile-user@m.gmane-mx.org; Sun, 22 Nov 2020 13:48:40 -0500 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:57802) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1kguPY-0002Zl-09 for guile-user@gnu.org; Sun, 22 Nov 2020 13:48:32 -0500 Original-Received: from mout01.posteo.de ([185.67.36.65]:37464) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1kguPV-0000uz-9r for guile-user@gnu.org; Sun, 22 Nov 2020 13:48:31 -0500 Original-Received: from submission (posteo.de [89.146.220.130]) by mout01.posteo.de (Postfix) with ESMTPS id 2A8C8160060 for ; Sun, 22 Nov 2020 19:48:25 +0100 (CET) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=posteo.de; s=2017; t=1606070906; bh=991gR23MDqdFsZPLyUmm6BEZjWsmELlGidfTsWtyNDg=; h=To:From:Subject:Date:From; b=SX+tVH5n0kJuwqlWCiY2NDzks6/yc+k2gmqIKEZUGZCKycazL031jEEDI8KvRNJKk /gPBArPW9yPKl4jdAMEG/D6qg9+w0Qy/f3laCmB57IL1LkOvQRiSfaTb2nwFRZaNZD 0YJPtIwFtYm5YlVMvey/Jo+XcyXUxCyQm1iS4R13FR8hizN6TrnpaivAqNHpSeV8Ek AwnSAtguDRz+jxNm7MdGNyr5eYkHeaoWu5Rd64DfOs7kuJXV7115nZ0yleUiapZmLb lez3oevFLysxVI5J7Nwrgm78L38Kuqf/ucrv3y9c2ukihKyj8m3w3UYwn7jFj9/FoH v7pDW8Le/NOBg== Original-Received: from customer (localhost [127.0.0.1]) by submission (posteo.de) with ESMTPSA id 4CfK6x4DL9z9rxM for ; Sun, 22 Nov 2020 19:48:25 +0100 (CET) Content-Language: en-US Received-SPF: pass client-ip=185.67.36.65; envelope-from=zelphirkaltstahl@posteo.de; helo=mout01.posteo.de X-Spam_score_int: -43 X-Spam_score: -4.4 X-Spam_bar: ---- X-Spam_report: (-4.4 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, RCVD_IN_DNSWL_MED=-2.3, RCVD_IN_MSPIKE_H4=-0.01, RCVD_IN_MSPIKE_WL=-0.01, 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:17034 Archived-At: 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 -- repositories: https://notabug.org/ZelphirKaltstahl