Hello,
Someone on the LISP HUG Mailing list was recently trying to allocate a 4GB array and found that it was failing. I was recently thinking about such problems wishing there were sparse arrays in CL; I ended up making something called ’Spaces’ which potentially solve the problem.
Below is a letter to HUG that I sent to someone outlining my solution to the problem.
I thought some of you might find it useful as well, or might want to discuss this data structure, which I think is new, or at least I have never read nor heard of it before I invented it a couple of months ago.
Burton
Begin forwarded message:
From: Burton Samograd busfactor1@icloud.com Subject: Re: Creating large arrays Date: July 18, 2019 at 2:45:14 PM MDT To: lisp@gmx.com Cc: lisp-hug@lispworks.com
Are there other fast-access data structures with no such limitations, on LispWorks?
Thank you again,
Priyadarshan
I have created something called ’N-Dimensional Sparse Spaces’ as a solution to the large array allocation problem.
This initial implementation is one to replace a set of random points within an N-Dimensional Sparse Grid addressed using integers, hence the use of #’= in #’make-space.
It is more generallized using other equals functions such as #’eql (so you can use symbols, and hence make an addressable symbol space), #’equals and #equalp letting you use S-Expressions as your addresses.
I have a more general implementation somewhere in my code, but the above image is the code I initially wrote that can be springboarded off of to create your own implementation.
One trick I have thought of is to, after you have completed your work with the space, is to compile it to a more suituable data structure for read-only access.
The sparce space is for editing and loading of the data you want to work with. A complied space is for reading data from the space, giving up generality.
Feel free to write me to discuss this data structure further if you have any questions or comments on its usefulness and generality and applicability to your problem.
Burton Samograd BusFactor1 Inc.
