Python中的ast模块允许多种遍历策略，我想了解的是，当选择一种特定的遍历方式时，在复杂性方面是否有显著的提高？
下面是两个例子：
- 示例1**
class GlobalVisitor(ast.NodeTransformer):
def generic_visit(self, tree):
for node in tree.body:
if isinstance(node, ast.Global):
*transform the ast*- 示例2**
class GlobalVisitor(ast.NodeTransformer):
def visit_Global(self, tree):
*transform the ast*在例1中，我重写了generic_visit方法，提供了我自己的遍历树的实现，但是这是通过访问树体中的每个节点来实现的，所以O（n）。
在例2中，我重写了visit_Global，这样就可以立即处理所有Global类型的节点，这就是ast的工作原理。
我想知道，在示例2中，ast是否可以通过重写visit_* field *（self，node）对我指定的节点进行即时的**O（1）访问，或者它只是在O（n）**中再次遍历树，在后台查找我需要的节点，从而稍微简化了我的工作？
1条答案
按热度按时间djmepvbi1#
@metatoaster、@user2357112和@rici提供的评论中的一些要点：
**1.**示例1完全错误。不应以所描述的方式遍历树为目标，因为在
tree.body上迭代是完全错误的-tree.body不是AST中每个节点的集合，它是Module节点的一个属性，为模块中的顶级语句提供了节点列表。它将错过每一个重要的global语句（因为除非出现非常奇怪的exec情况，否则正确的global语句永远不会是顶级的），它将在非模块节点输入时崩溃。如果要实现示例1的正确版本，只需使用ast.iter_child_nodes递归迭代即可。但是，请注意iter_child_nodes的名称是正确的。它不是iter_descendant_nodes。它只访问直接子代。递归遍历必须在对每个子代执行的操作中实现。
**2.**如果正确实现，两种方法是等效的，并且意味着递归遍历，但是覆盖visit_type（self，node）可以节省一些时间。在复杂性方面不会获得任何好处。
**3.**如果您想更改AST，则仅使用NodeTransformer，否则仅使用NodeVisitor。
最后，
ast的文档似乎不够详尽，请参考this以获取更详细的文档。它有点过时（大约一年），但比原始的ast更好地解释了一些基本原理。