Hello,
I need an efficient data strucuture to work with trees in Lisp. IIRC,
using Lisp lists is not ideal because it is not efficient as a data
structure.
I'm thinking about having trees of more than 1000 nodes. And they will
not be binary, any node can have an arbitrary number of children.
Any suggestions?
·········@gmx.net (thelifter) writes:
> Hello,
>
> I need an efficient data strucuture to work with trees in Lisp. IIRC,
> using Lisp lists is not ideal because it is not efficient as a data
> structure.
> I'm thinking about having trees of more than 1000 nodes. And they will
> not be binary, any node can have an arbitrary number of children.
>
> Any suggestions?
You could use a vector, or use a hash-table as a sparse vector, or as
a hash-table. Or even use the object system; a few thousand objects
isn't all that much, depending. I highly recommend looking at a good
algorithms/data-structures text. The issue of how to represent a tree
is fairly language-neutral, and a good text should have a variety of
ways, allowing you to pick the best one for your needs (which aren't
elaborated in your post).
--
/|_ .-----------------------.
,' .\ / | No to Imperialist war |
,--' _,' | Wage class war! |
/ / `-----------------------'
( -. |
| ) |
(`-. '--.)
`. )----'
In article <····························@posting.google.com>,
thelifter <·········@gmx.net> wrote:
>I need an efficient data strucuture to work with trees in Lisp. IIRC,
>using Lisp lists is not ideal because it is not efficient as a data
>structure.
>I'm thinking about having trees of more than 1000 nodes. And they will
>not be binary, any node can have an arbitrary number of children.
You could use a vector to store the references to all the children. This
will typically use about half as much memory as a list.
--
Barry Margolin, ······@genuity.net
Genuity, Woburn, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.
From: Jeff Sandys
Subject: Re: Efficient data structure for TREES in LISP
Date:
Message-ID: <3DFA3971.ABFF66A8@juno.com>
thelifter wrote:
>
...
> using Lisp lists is not ideal because it
> is not efficient as a data structure.
Why?
From: Tim Bradshaw
Subject: Re: Efficient data structure for TREES in LISP
Date:
Message-ID: <ey3n0n88xc0.fsf@cley.com>
* Jeff Sandys wrote:
> Why?
linear not constant (or log maybe) access time to the various
children. Same problem as with using lists as arrays.
--tim