我正在尝试在AST（抽象语法树）中搜索特定节点。基本思想是：
- 有一个从源代码中解析的AST，其中包含大约10000个节点
- 我想在AST中搜索50个项目
问题：在AST中搜索这50个项目的最佳方式是什么？
现在，我正在考虑使用包含这50个项目的Arraylist。然后，遍历AST并使用循环将每个节点与Arraylist进行比较。就性能而言，这是个好主意吗？我希望手术能尽快完成。有其他方法可以解决这个问题吗？
我不会使用Arralylist，因为它需要每次扫描它，这只是开销。您可以同样容易地将50个谓词写成"p1或p2或…"。
你可以搜索树一次，应用50个谓词来决定你是否有一个感兴趣的节点，也可以搜索树50次，在每个单独的过程中应用一个谓词。在这两种情况下，你都必须运行谓词，这样它们都不会改变成本（请注意）。
如果你搜索一次，你需要将50个谓词的答案"或"放在一起，需要49个or，所以额外的成本是49*[or的成本][节点数]。如果搜索50，则额外成本为49[访问树节点的成本]*[节点数]。因此，问题是"或"的成本是否小于"访问树节点"的成本。"Or"在大多数机器上都很快，因为它只使用可能已经在缓存中的寄存器和值。访问一个树节点可能很快，但可能需要几个指令；更糟糕的是，它触动了记忆。如果你的树足够大，不适合缓存，那么如果谓词很便宜，你的搜索50成本可能会由内存访问时间决定。
现在，我们可以用一些有趣的方式"作弊"。首先，可能是谓词之间存在一些关系；如果谓词A暗示谓词B，我可以先检查B，如果为false，我不必测试A。这可以减少"或"的数量，但对树访问没有帮助。其次，可能是谓词共享子测试，例如，谓词A实际上是"a1和a2"，而B实际上是"a1和a2"；在这种情况下，您可以对谓词进行因子化，并减少对子谓词的求值次数；每个节点只需要对"a1"求值一次。使用多重扫描技术可不容易做到这一点。可能是某些谓词失败意味着不需要搜索子树；在这里，50次搜索可能会更快，因为每次搜索都只检查必要的子树，其中一次搜索几乎需要搜索到所有谓词都一致认为是停止点的节点。
然而，对于每个谓词，您的程序可能希望做出不同的反应。所以你的程序结构实际上是一组"如果p1（节点），那么a1（节点）"。如果谓词价格低廉且触发频率相对较高，那么操作可能是主要成本（比导航树节点更贵），那么就性能而言，这两种技术都很好。
最后，如果谓词和操作很复杂，您可能无法简单地猜测哪一个更便宜。好吧，对两个搜索进行编码（不是很难），并在实际数据上进行测量。