Это продолжение кодин из моих предыдущих постов.

Я пытался понять, почемуRuleTransformer производительность такая плохая. Теперь я считаю, что это так медленно, потому что его сложность O (2n), где 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 посещаетсявосемь раз.

Если мы преобразуем<a4><a3><a2><a1/></a2></a3></a4> затемa1 посетят 16 раз, для<a5><a4><a3><a2><a1/></a2></a3></a4></a5> - 32 и т. Д. Так выглядит сложностьэкспоненциальный.

Имеет ли это смысл ? Как бы вы доказали это путем анализакод ?