我有一组深度在 20 年代某处的树对象。这棵树中的每个节点都需要访问其树的根。
几个解决方案：
- 每个节点可以直接存储对根的引用（浪费内存）
- 我可以通过“上升”（浪费周期）在运行时计算根
我可以使用静态字段（但这相当于全局）
有人可以提供一种不使用全局（在任何变体中）但在内存或周期中分别比 #1 或 #2 更有效的设计吗？
编辑：由于我有一组树，我不能简单地将它存储在静态中，因为很难区分树。（感谢麦克库尔特）
Allain Lalonde
问问题
417 次
6 回答
6
将根作为参数传递给节点中需要它的任何函数。
编辑：选项实际上如下：
- 将根引用存储在节点中
- 根本不存储根引用
- 将根引用存储在全局中
- 将根引用存储在堆栈上（我的建议，访问者模式或递归）
我认为这是所有可能性，没有选项5。
于 2008-09-16T00:16:39.153 回答
3
为什么需要取消全局变量？我理解全局变量的污名是坏的，但有时仅仅拥有一个包含所有元素的全局数据结构是最快的解决方案。
您进行了权衡：代码清晰，未来的性能问题更少。这就是'不要优化'的意思。由于您处于优化阶段，因此有时有必要删除一些可读性和良好的编程实践以提高性能。我的意思是，按位破解是不可读的，但它们很快。
我不确定你有多少树对象，但我个人会选择选项一。除非您要处理数千棵树，否则指针实际上不会超过几个字符串。如果内存确实是一个非常重要的问题，请尝试这两种方法（它们似乎很容易实现）并通过分析器运行它。或者使用优秀的Process Explorer。
编辑：我正在开发的一个应用程序有一个包含大约 55K 节点的节点树。我们构建了树结构，但也维护了一个用于 O(1) 查找的数组。比我们在使用递归 FindNodeByID 方法时得到的 O(m*n) 好得多。
于 2008-09-16T00:19:13.297 回答
2
将根作为参数传递通常是最好的。如果您使用某种迭代器来导航树，另一种方法是在其中存储对 root 的引用。
于 2008-09-16T00:38:24.297 回答
1
第 1 点是过早的内存优化。#2 是过早的性能优化。您是否分析过您的应用程序以确定内存或 CPU 瓶颈是否给您带来了问题？如果不是，为什么要牺牲一个更可维护的设计来进行对用户没有帮助的“优化”？
我强烈建议您使用#2。每当你存储一些你可以计算的东西时，你所做的就是缓存。有几次缓存是一个好主意，但它也是一个令人头疼的维护问题。（例如，如果您通过更改其父节点将节点从一棵树移动到另一棵树，但忘记更新根字段怎么办？）如果不需要，请不要缓存。
于 2008-09-16T00:27:53.200 回答
0
您可以从 TreeView 派生一个类，然后添加一个单例静态属性。这样，您就可以有效地添加一个引用该类的单个实例的全局字段，但可以将其命名空间范围限定为该类。
于 2008-09-16T00:31:00.557 回答
0
忽略对内部类的厌恶，我可以定义一个 Tree 类并将节点定义为内部类。每个节点都可以访问其树的状态，包括其根。
这可能最终与 #1 相同，具体取决于 Java 如何将节点与其父节点关联起来。（我不确定，我必须对其进行分析）
于 2008-09-16T00:37:30.603 回答