biopython/biopython — pull request #179 by bendmorris (2013-04-30 00:13:00+00:00)
Title: Refactoring BaseTree.py to optimize common_ancestor and distance functions

Re: https://redmine.open-bio.org/issues/3427

My workaround was still not fast enough, and @etal is right that I was re-computing parts of paths unnecessarily. I think I can do better.

If each tree node stores a pointer to its parent at object construction time, we can pay a slight upfront time/memory cost in order to increase the efficiency of the common_ancestor and distance functions dramatically. Instead of doing a depth-first search of the tree to find the path, we can start at the node of interest and easily trace it back up to the root by moving from parent to parent.

I just implemented this and ran a script that computed the distance between 50 random species pairs of the Bininda-Emonds mammal tree, then compared with the dev branch of BioPython. distance and common_ancestor are about 100x faster now.

Old version:

3957297 function calls (2856534 primitive calls) in 2.304 seconds

ncalls tottime percall cumtime percall filename:lineno(function)
1 0.056 0.056 0.160 0.160 NewickIO.py:113(_parse_tree)
300/100 0.001 0.000 1.266 0.013 BaseTree.py:459(distance)
150 0.003 0.000 1.430 0.010 BaseTree.py:401(common_ancestor)

New version:

479215 function calls (364071 primitive calls) in 0.490 seconds

ncalls tottime percall cumtime percall filename:lineno(function)
1 0.058 0.058 0.199 0.199 NewickIO.py:113(_parse_tree)
100 0.001 0.000 0.010 0.000 BaseTree.py:464(distance)
150 0.001 0.000 0.017 0.000 BaseTree.py:405(common_ancestor)

Thoughts? Hopefully I didn't just break anything. All the tests seem to be passing still.