废除全局变量？

Question

我有一组深度在 20 多岁的树对象。该树中的每个节点都需要访问其树的根。

几个解决方案：

1. 每个节点可以直接存储对根的引用（浪费内存）
   • 我可以通过“向上”（浪费循环）在运行时计算根
   • 我可以使用静态字段（但这相当于全局变量）

有人可以提供一种不使用全局（任何变体）但在内存或周期上分别比 #1 或 #2 更高效的设计吗？

编辑： 由于我有一组树，我不能简单地将其存储在静态中，因为很难区分树。（谢谢麦考特）

Answer 1

将根作为参数传递给节点中需要它的任何函数。

编辑：选项实际上如下：

1. 将根引用存储在节点中
2. 根本不存储根引用
3. 将根引用存储在全局中
4. 将根引用存储在堆栈上（我的建议，访问者模式或递归）

我觉得这都是可能，没有选项5。

Answer 2

为什么需要取消全局变量？我理解全局变量不好的耻辱，但有时仅仅拥有一个包含所有元素的全局数据结构就是最快的解决方案。

你做出一个权衡：代码清晰，未来的性能问题更少。这就是“暂时不要优化”的意思。由于您处于优化阶段，有时有必要删除一些可读性和良好的编程实践以提高性能。我的意思是，按位 hack 不可读，但速度很快。

我不确定你有多少个树对象，但我个人会选择选项一。除非您要处理数千棵树，否则指针实际上不会比几个字符串多多少。如果内存确实是一个非常重要的问题，请尝试这两种方法（它们似乎实现起来相当简单）并通过分析器运行它。或者使用优秀的 流程浏览器.

编辑：我正在开发的应用程序之一有一个包含大约 55K 个节点的节点树。我们构建树结构，但也维护一个用于 O(1) 查找的数组。比我们使用递归 FindNodeByID 方法时获得的 O(m*n) 好得多。

Answer 3

通常最好将根作为参数传递。如果您使用某种迭代器来导航树，另一种方法是在其中存储对根的引用。

Answer 4

第一点是过早的内存优化。#2 是过早的性能优化。您是否对您的应用程序进行了分析以确定内存或 CPU 瓶颈是否给您带来了问题？如果不是，为什么要为了对用户没有帮助的“优化”而牺牲更易于维护的设计呢？

我强烈建议你选择#2。每当你存储一些可以计算的东西时，你所做的就是缓存。有时缓存是个好主意，但它也是一个令人头痛的维护问题。（例如，如果通过更改父节点将节点从一棵树移动到另一棵树，但忘记同时更新根字段，该怎么办？）如果不需要，请不要缓存。

Answer 5

您可以从 TreeView 派生一个类，然后添加一个单例静态属性。这样，您就可以有效地添加一个全局字段，该字段引用该类的单个实例，但具有其命名空间范围仅限于该类的优点。

Answer 6

忽略对内部类的厌恶，我可以定义一个 Tree 类并将节点定义为内部类。每个节点都可以访问其树的状态，包括其根。

这可能最终与#1 相同，具体取决于 Java 如何将节点与其父节点相关联。（我不确定，我必须对其进行分析）