Does D have "structural sharing" of immutable collections?
Roman D. Boiko
rb at d-coding.com
Wed May 23 15:39:33 PDT 2012
On Wednesday, 23 May 2012 at 22:25:35 UTC, Steven Schveighoffer
wrote:
> I looked up how it could be done, the one thing I was not sure
> of was the parent node. If you can have multiple references to
> the same subtree, how do you keep track of the parents. But if
> you only are concerned about the ancestry of a single node, you
> can dynamically determine the line in O(lgn) time, and use that
> for the running of the redblack algorithm.
>
> I'm not sure how efficient it would be.
>
> -Steve
My problem is the following:
n elements in some given order, each has an associated value; I
need to retrieve elements for which the sum of values associated
with previous elements lies in a given ragne; this should work
efficiently when elements are added or removed, and history
should be preserved.
Storing elements as tree leafs and sums of children values in
other nodes gives me this easily.
Lookup price is 0(log N) number comparisons, which should be very
fast. Insert / delete / rotate are also logarithmic, but I don't
know the constant factors.
No need to retrieve parents.
So far it seems like RBT is perfect for me (if cache friendly
implementation will be possible. Hopefully it will, because nodes
are small and I can preallocate memory for them).
More information about the Digitalmars-d
mailing list