Re: Data Structure for use vs storage
"Marco Antoniotti (as marco dot antoniotti at unimib dot it)" <[email protected]>
| Newsgroups | gmane.lisp.lispworks.general |
|---|---|
| Message-ID | <CAG0Nw2kMD9J9MP2VsqxsA1nndS8XTfa1-MfseFV+QF0YGMnpaA@mail.gmail.com> |
If you do not need ordering, just use a hash table. Red Black trees? Shameless plug: https://www.cs.cmu.edu/afs/cs/project/ai-repository/ai/lang/lisp/code/ext/trees/ Yes. I *am* old. I also have a cute Skip list implementation floating around. Cheers MA On Wed, Feb 18, 2026 at 9:51 AM David McClain (as dbm at refined-audiometrics dot com) <[email protected]> wrote: > > In addition to a hashtable, you can maintain a BTree index on a "primary > key" column. That would considerably speed up queries like this: > > > > (bplustree-search-range 501 1000 *my-tree*) > > > > > Yes, true. But there again you are assuming an ordering relation for the > key. > > And to avoid problems with multiprocessing, I would instead use a purely > functional Red-Black tree. > > Why Red-Black? Well you’d have to ask the computer scientists that > invented the OCaml standard library. I just translated what they provided > there into Lisp. (IOW, I cheated…) > > But purely functional has huge advantages in the face of parallel and > multiple thread concurrent access. And no locks needed. > > > > > On Feb 18, 2026, at 00:17, Dmitry Ivanov (as ystok-systema at mail dot > ru) <[email protected]> wrote: > > > > David McClain (as dbm at refined-audiometrics dot com) wrote: > > > >> I looked at the BTree code. Interesting. But when would you use this > over the built-in Hashtables of Common Lisp? In fact, with Hashtables, you > don’t even need an ordering to the underlying data, just an equality > comparison. > > > > In addition to a hashtable, you can maintain a BTree index on a "primary > key" column. That would considerably speed up queries like this: > > > > (bplustree-search-range 501 1000 *my-tree*) > > > > -- > > Dmitry Ivanov > > lisp.ystok.ru > > > > _______________________________________________ > > Lisp Hug - the mailing list for LispWorks users > > [email protected] > > http://www.lispworks.com/support/lisp-hug.html > > > _______________________________________________ > Lisp Hug - the mailing list for LispWorks users > [email protected] > http://www.lispworks.com/support/lisp-hug.html > -- Marco Antoniotti, Professor, Director tel. +39 - 02 64 48 79 01 DISCo, University of Milan-Bicocca U14 2043 http://dcb.disco.unimib.it Viale Sarca 336 I-20126 Milan (MI) ITALY REGAINS: https://regains.disco.unimib.it/