Doing away with Globals?

Question

I have a set of tree objects with a depth somewhere in the 20s. Each of the nodes in this tree needs access to its tree's root.

A couple of solutions:

1. Each node can store a reference to the root directly (wastes memory)
2. I can compute the root at runtime by "going up" (wastes cycles)
3. I can use static fields (but this amounts to globals)

Can someone provide a design that doesn't use a global (in any variation) but is more efficient that #1 or #2 in both memory or cycles respectively?

Edit: Since I have a Set of Trees, I can't simply store it in a static since it'd be hard to differentiate between trees. (thanks maccullt)

Answer 1

Pass the root as a parameter to whichever functions in the node that need it.

Edit: The options are really the following:

1. Store the root reference in the node
2. Don't store the root reference at all
3. Store the root reference in a global
4. Store the root reference on the stack (my suggestion, either visitor pattern or recursive)

I think this all the possibilities, there is no option 5.

Answer 2

Why would you need to do away with globals? I understand the stigma of globals being bad and all, but sometimes just having a global data structure with all elements is the fastest solution.

You make a trade-off: code clarity and less future problems for performance. That's the meaning being 'Don't optimize yet'. Since you're in the optimize stage, sometimes it's necessary to cut out some readability and good programming practices in favor of performance. I mean, bitwise hacks aren't readable but they're fast.

I'm not sure how many tree objects you have, but i'd personally go with option one. Unless you're dealing with thousands+ of trees, the pointers really won't amount to much more then a few strings. If memory really is a super-important issue, try both methods (they seem fairly simple to implement) and run it through a profiler. Or use the excellent Process Explorer.

Edit: One of the apps I'm working on has a node tree containing about 55K nodes. We build the tree structure but also maintain an array for O(1) lookups. Much better then the O(m*n) we were getting when using a recursive FindNodeByID method.

Answer 3

Point #1 is a premature memory optimization. #2 is a premature performance optimization. Have you profiled your app to determine if memory or CPU bottlenecks are causing problems for you? If not, why sacrifice a more maintainable design for an "optimization" that doesn't help your users?

I would strongly recommend you go with #2. Whenever you store something you could instead calculate, what you are doing is caching. There's a few times when caching is a good idea, but it's also a maintenance headache. (For example, what if you move a node from one tree to another by changing its parent but forget to also update the root field?) Don't cache if you don't have to.

Answer 4

You could derive a class from TreeView and then add a singleton static property. That way you are effectively adding a global field that references the single instance of the class but have the benefit of it being namespace scoped to that class.

Answer 5

Ignoring the distaste for inner classes, I could define a Tree class and define the nodes as Inner classes. Each of the nodes would have access to its tree's state including its root.

This might end up being the same as #1 depending on how Java relates the nodes to their parents. (I'm not sure and I'll have to profile it)

Answer 6

Passing the root as a paramter is generally best. If you're using some kind of iterator to navigate the tree, an alternative is to store a reference to root in that.