ITADN

Partial recursion unrolling for PreOrderIter

#278Pull Requestgregreich 创建于 2025-09-21
G
gregreichcommented
Occasionally, I have trees that are very degenerate in the sense that they feature an overwhelming majority of "only-child" parents; let's call those trees "sparse" in this context. In my application, the sparseness is inherent already in the physical domain that I model, and is thus costly to avoid in the code. Now, for large trees, important standard operations that build on recursion—such as the iterators—can blow up the Python recursion stack; at the same time, the latter can no longer simply be increased without tricks (see, for example, [this discussion](https://stackoverflow.com/questions/5061582/setting-stacksize-in-a-python-script/16248113#16248113)). One way to avoid this is to "unroll" all those recursions that are degenerate in that they do not incorporate any branching. I have implemented that in `PreOrderIter` exemplarily, and added some more unit tests that capture cases that haven't been covered before. This *partial* unrolling implementation is a compromise between loop and recursion: of course, the queue (or the stack) approach could be used even more consequently, eliminating all recursion whatsoever. However, this would particularly complicate the "maxlevel" filtering, having it to rely on (more expensive) calls to the `depth` property. At the same time, the most obviously unnecessary recursion is effectively avoided, making the iterator significantly more efficient for sparse—yet large—trees. One final remark about this pull request: For now, I only updated `PreOrderIter`, for one thing because I mostly use this iterator in my own work, and for another because it is heavily used internally. This latter use is what made me submit this PR: In my understanding, there is no way to "augment" anytree by a new iterator implementation through delegation or inheritance, which also replaces its internal use in standard properties, such as `leaves`, `size`, etc.
合并状态:未合并 1 条评论