On Monday, 12 August 2019 at 22:48:43 UTC, Bert wrote:
Making a field static is effectively a global variable to the
class.
I have a recursive class structure(think of a graph or tree)
and I need to keep a global state for it, but this state
actually needs to be different for each tree object. The reason
for this is that structurally it will not change per tree and
if it it is not static then it wastes space unnecessarily.
class X
{
X[] x;
static State s;
}
making s non-static has the problem that every X will allocate
storage for s wasting space since for any instance chain of X's
they will all have the same s. Making it static though then
makes it the same for all instance chain's of X, of which it
should be local to each.
One way around this is to use an dictionary that associates
each state to each instance chain.
That is there is a initial X that is the parent of the chain
and we can then associate a state to it's address, any other
chain will have a different initial X and so we can get a new
state.
class X
{
X[] x;
static State[X] s;
}
This is not a huge difficulty to do but does require finding
the initial X to use, which is not difficult but wastes cycles
for large chains. There will, of course, be a constructor that
constructs a chain and creates a new state for it and updates s.
Is there any way to do this more naturally in D?
First: Are you low on memory? Is traversing the tree actually
slow? Since you don't know which of these issues to prioritize,
in all likelihood the answer to both questions is no, and you
should use the solution that's easier to read.
Of course, that's not the answer you want to hear. Let's consider
the alternatives:
1) Embed it in each node. Costs 1 pointer's worth of memory per
node. Very fast. Very easy to understand.
2) Use a dictionary with entries for each node. Costs more than 1
pointer's worth of memory per node. Fast, but not quite as fast
as 1). 1) is almost definitely a better option.
3) Use a dictionary with entries for each root node. Costs more
than 1 pointer's worth of memory, but per tree instead of per
node. Requires traversal of the tree to find the root, so slower
than both 1) and 2), especially for deep hierarchies. Complicated
code.
4) Use a derived class for the root node (class RootX : X { State
s }). Still requires traversing the tree to find the root, likely
via a virtual method. Also requires a bit more work setting up
the tree. Might be faster than 3), definitely smallest memory
footprint. Relatively easy to follow.
There may be other options, but from the above I'd go with either
1) or 4).
Now, I've noticed that X doesn't have a pointer to its parent, so
traversing the tree to find the root is currently impossible. If
this is true, and you have no other use for traversing up the
tree, then 1) is the way to go, as 2) is almost never a better
option, and 3) and 4) requires adding a parent pointer so you'll
pay the memory price anyway.
--
Simen
