这是后续one我以前的帖子。
I tried to understand why the RuleTransformer performance is so poor. Now I believe that it is so slow because its complexity is O(2n), where n is the height of the input XML tree.
假设我需要将所有元素的所有标签重命名为标签“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>
So a1
被访问eight times.
如果我们转型<a4><a3><a2><a1/></a2></a3></a4>
then a1
将被访问 16 次,因为<a5><a4><a3><a2><a1/></a2></a3></a4></a5>
-- 32 等。所以复杂度看起来指数.
是否有意义 ?你如何通过分析证明这一点code ?