javalang icon indicating copy to clipboard operation
javalang copied to clipboard

getCommonAncestor is potentially slow

Open sch-cbavel opened this issue 7 years ago • 0 comments

https://github.com/rpau/javalang/blob/cacae3667dec88f9c2955858fa2a0fe1d73bc0d3/src/main/java/org/walkmod/javalang/ast/Node.java#L353-L367

Right now it is O(N^2) for the worst case where N is the nesting level. You can reduce one order of magnitude O(3*N) in the worst case. You just have to calculate the nesting level. Just go to the root node for both nodes, so you have the depth. Once you have it, get the deepest node and go until the level matches the other one. Then move upwards both nodes until you reach the common node.

sch-cbavel avatar Nov 23 '17 15:11 sch-cbavel