在我的代码中,Java TreeSet迭代是主要的时间因素。在查看系统时,我认为它是 O(n) 复杂度。任何人都可以验证这一点吗?
我在想,通过提供从子节点到父节点的反向链接,我可以提高性能。
在我的代码中,Java TreeSet迭代是主要的时间因素。在查看系统时,我认为它是 O(n) 复杂度。任何人都可以验证这一点吗?
我在想,通过提供从子节点到父节点的反向链接,我可以提高性能。
TreeSet
迭代当然是 O(n),正如任何明智的树行走算法所期望的那样。
我在想,通过提供从子节点到父节点的反向链接,我可以提高性能。
TreeMap
(TreeSet
基于)已经有这样的父引用。这就是它归结为的方法:
private Entry<K,V> successor(Entry<K,V> t) {
if (t == null)
return null;
else if (t.right != null) {
Entry<K,V> p = t.right;
while (p.left != null)
p = p.left;
return p;
} else {
Entry<K,V> p = t.parent;
Entry<K,V> ch = t;
while (p != null && ch == p.right) {
ch = p;
p = p.parent;
}
return p;
}
}
您是否考虑在更改 TreeSet 时复制它?如果支配时间花费在 TreeSet 迭代中(而不是修改它),那么将 TreeSet 复制到数组或 ArrayList(仅在更改时)并且仅在此数组/ArrayList 上进行迭代几乎可以消除 TreeSet 迭代的成本。