Matt - thanks for the help making the FFI pointers work! On Sun, Nov 22, 2020 at 10:44 PM <guile-user-requ...@gnu.org> wrote:
> Send guile-user mailing list submissions to > guile-user@gnu.org > > To subscribe or unsubscribe via the World Wide Web, visit > https://lists.gnu.org/mailman/listinfo/guile-user > or, via email, send a message with subject or body 'help' to > guile-user-requ...@gnu.org > > You can reach the person managing the list at > guile-user-ow...@gnu.org > > When replying, please edit your Subject line so it is more specific > than "Re: Contents of guile-user digest..." > > > Today's Topics: > > 1. Re: Question about data structures (Tim Van den Langenbergh) > 2. broken link on "Learn" page (Tim Meehan) > 3. Re: Guile dynamic FFI, C function expecting pointer (Matt Wette) > 4. Re: Question about data structures (Taylan Kammer) > 5. Re: Question about data structures (John Cowan) > > > ---------------------------------------------------------------------- > > Message: 1 > Date: Sun, 22 Nov 2020 23:50:47 +0100 > From: Tim Van den Langenbergh <tmt_...@gmx.com> > To: guile-user@gnu.org > Subject: Re: Question about data structures > Message-ID: <4033601.nszuQzh3Xh@terra> > Content-Type: text/plain; charset="utf-8" > > 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 > -------------- next part -------------- > A non-text attachment was scrubbed... > Name: signature.asc > Type: application/pgp-signature > Size: 833 bytes > Desc: This is a digitally signed message part. > URL: < > https://lists.gnu.org/archive/html/guile-user/attachments/20201122/ad299977/attachment.sig > > > > ------------------------------ > > Message: 2 > Date: Sun, 22 Nov 2020 16:56:56 -0600 > From: Tim Meehan <btmee...@gmail.com> > To: guile-user@gnu.org > Subject: broken link on "Learn" page > Message-ID: > < > cacgrox+2v+qgp5vezzaxbongear5x0sxlj19xqaswkor5zg...@mail.gmail.com> > Content-Type: text/plain; charset="UTF-8" > > There is a broken link to the "Internet Scheme Repository" on the "Learn" > page of the GNU Guile website: > https://www.gnu.org/software/guile/learn/ > > I didn't see a contact email on the website, but I figured that someone > here might know someone that ran the website ... if not, my apologies. > > > ------------------------------ > > Message: 3 > Date: Sun, 22 Nov 2020 16:16:47 -0800 > From: Matt Wette <matt.we...@gmail.com> > To: guile-user@gnu.org > Subject: Re: Guile dynamic FFI, C function expecting pointer > Message-ID: <da5a069d-d156-6f69-386e-50b9364c7...@gmail.com> > Content-Type: text/plain; charset=utf-8; format=flowed > > > > On 11/22/20 2:50 PM, Tim Meehan wrote: > > I tried to boil this question down to the most simple thing that > > represented what I needed to understand. I have had luck getting C > > functions that expect arguments "by value," but "by reference" has been > > problematic. > > > > The failure mode is "Segmentation Fault," so I gather that I may not be > > using the right Guile call at all. > > > > The Guile user manual is usually quite excellent, but I seem to be > missing > > something important. > > > > Thanks, > > > > > ;;----------------------------------------------------------------------------;; > > ;; C source for "libstuff.so": > > ;; file stuff.c, compiled as: > > ;; gcc stuff.c -o libstuff.so -fPIC -shared > > #| > > void int_ptr_example1(int *a) { > > *a = 5; > > } > > |# > You'll need to make-bytevector a bytevector that holds sizeof(int) bytes. > Then pass (bytevector->pointer <obj>) as the argument. > > (let ((obj (make-bytevector (sizeof int)))) > (int-ptr-example (bytevector->pointer obj))) > > Now the 5 should be in the bytevector. You will need to extract it. > > > > > > > ------------------------------ > > Message: 4 > Date: Mon, 23 Nov 2020 04:42:37 +0100 > From: Taylan Kammer <taylan.kam...@gmail.com> > To: Zelphir Kaltstahl <zelphirkaltst...@posteo.de>, Guile User > <guile-user@gnu.org> > Subject: Re: Question about data structures > Message-ID: <a5317e0c-9fe0-1fb9-c6b5-d3065d179...@gmail.com> > Content-Type: text/plain; charset=utf-8; format=flowed > > On 22.11.2020 19:48, Zelphir Kaltstahl wrote: > > Hello Guile Users! > > > > I have a question about data structures. > > > > [...] > > > > How do you approach this problem? Is it a problem at all? > > First of all, be cautious about premature optimization. In many cases > it's best to just write the code the most straightforward way possible > with the tools at hand, and not bother with optimization unless it > actually proves to be an issue. Are you going to be processing files > with millions of lines? Thousands of lines but on a very weak CPU? > Does it matter if your program takes 0.1 seconds or 2 seconds to run? > > > Now the actual answer, in case you need to optimize, or just want to > learn more: > > > All data structures that offer a sequential list of elements have to > make some trade-offs between the performance of various operations, as > well as the implementation complexity. Linked lists (i.e. "lists" in > Scheme) are very simple, and a few operations are cheap as well, but > they have the shortcomings you've described plus some more. > > > 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. > > > 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. > > > The VList has also been mentioned in this thread, but from what I can > tell it doesn't seem to offer a very efficient append operation. > > > - Taylan > > > > ------------------------------ > > Message: 5 > Date: Sun, 22 Nov 2020 23:42:44 -0500 > From: John Cowan <co...@ccil.org> > To: Taylan Kammer <taylan.kam...@gmail.com> > Cc: Zelphir Kaltstahl <zelphirkaltst...@posteo.de>, Guile User > <guile-user@gnu.org> > Subject: Re: Question about data structures > Message-ID: > <CAD2gp_RqX=UivHkLjD0NDGo3KJBdVjq+4hXVTR0zf3XM= > vf...@mail.gmail.com> > Content-Type: text/plain; charset="UTF-8" > > On Sun, Nov 22, 2020 at 10:43 PM Taylan Kammer <taylan.kam...@gmail.com> > 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 co...@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) > > > ------------------------------ > > Subject: Digest Footer > > _______________________________________________ > guile-user mailing list > guile-user@gnu.org > https://lists.gnu.org/mailman/listinfo/guile-user > > > ------------------------------ > > End of guile-user Digest, Vol 216, Issue 19 > ******************************************* >
