探讨: CHA的复杂度与实现优化
- CHA的dispatch的时候,是沿着继承树找父类的, 最坏情况就是找到root类(java.lang.Object)才有method实现,复杂度是
O(h)
, h为开始dispatch的深度. - virtual call的处理, 需要遍历所有的子类(子接口), 并且每个都需要dispatch沿着路径回父节点找method实现.
那么最坏情况下: 继承图退化成一个链,method只有root类实现了, 这个复杂度就是1+2+3+...+(n-1)\ =\ O(n^2)
(n为总节点个数).
考虑到CHA的本质是callsite的类C有可能指向其所有的子类实例, 所以子类所有的method实现都有可能. 那么就可以在BFS/DFS遍历的时候, 遇到实现的method(非abstract)就加到resolve的method集合里面即可, 避免所有的节点都调用dispatch. 这样复杂度就是O(n)
, 每个节点只需要访问一次.
因此我的实现是, virtual call的时候, 令callsite声明的类为C, resolve(cs) = BFS(C的后继)找到的所有的非abstract的method + dispatch(C). (dispatch C 可能不存在,因为C可能是接口或者抽象类).
当前是过了作业给的样例, 并且自己造的几个也过了. 但是我不确定这样考虑是否全面(会不会漏掉或者多找了method?).
感兴趣的同学可以在这个Issue讨论一下下