xml - scala.xml.RuleTransformer 的复杂性真的呈指数级增长吗？

Question

这是 one 的后续行动我以前的帖子。

我试图理解为什么 RuleTransformer性能太差了。现在我相信它之所以这么慢是因为它的复杂度是 O(2ⁿ)，其中 n 是输入 XML 树的高度。

假设我需要将所有元素的所有标签重命名为标签“b”:

import scala.xml._, scala.xml.transform._

val rule: RewriteRule = new RewriteRule() {
  override def transform(node: Node): Seq[Node] = node match {
    case e: Elem => e.copy(label = "b")
    case other => other
  }
}

def trans(node: Node): Node = new RuleTransformer(rule).apply(node)

让我们数一数 transform 出现了多少次访问输入中的每个节点 <a3><a2><a1/></a2></a3> .
为了计算访问次数，我们添加了一个缓冲区 visited , 最开始初始化，存储访问过的节点，最后打印。

import scala.collection.mutable.ListBuffer

// buffer to store visited nodes
var visited: ListBuffer[Node] = ListBuffer[Node]()

val rule: RewriteRule = new RewriteRule() {
  override def transform(n: Node): Seq[Node] = {
    visited append (n) // count this visit
    n match {
      case e: Elem => e.copy(label = "b")
      case other => other
    }
  }
}

def trans(node: Node): Node = {
  visited = ListBuffer[Node]() // init the buffer
  val r = new RuleTransformer(rule).apply(node)
  // print visited nodes and numbers of visits 
  println(visited.groupBy(identity).mapValues(_.size).toSeq.sortBy(_._2))
  r
}

现在让我们在 REPL 中运行它并查看 visited

scala> val a3 = <a3><a2><a1/></a2></a3>
a3: scala.xml.Elem = <a3><a2><a1/></a2></a3>

scala> trans(a3)
ArrayBuffer((<a3><b><b/></b></a3>,2), (<a2><b/></a2>,4), (<a1/>,8))
res1: scala.xml.Node = <b><b><b/></b></b>

所以 a1被访问了 8 次。

如果我们转换 <a4><a3><a2><a1/></a2></a3></a4>然后 a1将被访问 16 次，对于 <a5><a4><a3><a2><a1/></a2></a3></a4></a5> -- 32 等。所以复杂度看起来呈指数。

有意义吗？你如何通过分析 code 来证明它？ ？

Answer 1

这不是一个非常严格的分析，但问题似乎出在 BasicTransformer 的 transform(Seq[Node]) 方法 [1] 上。

对于改变的节点，子变换方法将被调用两次。由于这个原因，特别是在您的示例中，所有节点都将被调用两次。你是对的，高度为 h 的每个节点将被调用 2^(h-1) 次。另请注意，由于使用跨度和代码，最多一个节点的一个子节点将被调用两次，在特定示例中，节点的所有子节点将被调用两次。

只是为了验证这一点，为修改后的 RulesTransformer 编写了这些代码示例。 (我也可以覆盖 RulesTransformer。但无论如何)

// This is same as library RuleTransformer added with print statement
class CopiedRuleTransformer(rules: RewriteRule*) extends BasicTransformer {
    override def transform(n: Node): Seq[Node] = {
        println(n)
        rules.foldLeft(super.transform(n)) { (res, rule) => rule transform res }
    }
}

我修改后的 RuleTransformer

class MyRuleTransformer(rules: RewriteRule*) extends BasicTransformer {
    override def transform(n: Node): Seq[Node] = {
        println(n)
        rules.foldLeft(super.transform(n)) { (res, rule) => rule transform res }
    }  
    override def transform(ns:Seq[Node]): Seq[Node] = {
        ns.flatMap(n => transform(n))
    } 
}

这些代码仅用于演示目的。您可以将它们称为

new CopiedRuleTransformer(rule).apply(node)

或

new MyRuleTransformer(rule).apply(node)

[1] 行:34 https://github.com/scala/scala-xml/blob/master/src/main/scala/scala/xml/transform/BasicTransformer.scala