Trees that contain many branchpoints take a progressively longer time to generate as they become more complex. This is due to the time it takes to determine which branch segment is closest to any endpoint. The code up to version 0.0.7 did a linear scan through all the branch segments for each endpoint and while this was still fast enough for moderately sized trees (the time it takes doesn't explode exponentially because each iteration removes endpoints within kill distance of a branch) it took many seconds for a tree with thousand endpoints, short internode lengths and a short kill distance. In other words it got slow when the trees became interesting.
Version 0.0.8 (available on Github, click view raw to download) adds a significant speed up for larger trees (3-6 times depending on parameter settings). Quite complex tree skeletons can now be generated in a few seconds instead of half a minute or more (depending on the power of your pc of course. And remember, this is a pure python implementation so having multiple cores makes no difference, it's the raw speed of a single core that counts). Please note that because endpoints within kill distance are removed in a different order, trees generated in version 0.0.8 are not identical to trees generated in previous versions but their general appearance stays the same.
For the technically inclined: this speed up is realized by storing all branch segments in a kd-tree, so looking for a nearest neighbor now scales as the log of the number of branch segments instead of taking linear time. This is a very noticeable difference once your tree grows to hundreds or even thousands of branch segments. The kd-tree is a pure python implementation in its own, separate module kdtree.py that might be interesting for other applications as well.
No comments:
Post a Comment