La complessità di scala.xml.RuleTransformer è davvero esponenziale?

Question

Questo è un follow-up di one dei miei post precedenti.

Ho cercato di capire perché le prestazioni dello RuleTransformer sono così scadenti. Ora credo che sia così lento perché la sua complessità è O (2 ⁿ), dove n è l'altezza dell'albero XML di input.

Supponiamo che ho bisogno di rinominare tutte le etichette di tutti gli elementi di etichettare "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) 

Contiamo quante volte i transform visite ogni nodo di ingresso <a3><a2><a1/></a2></a3>.
Per contare le visite aggiungiamo un buffer visited, inizialo all'inizio, memorizza i nodi visitati e stampalo alla fine.

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 
} 

Ora corriamo in REPL e vedere il 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> 

Così a1 è visitato otto volte.

Se trasformiamo <a4><a3><a2><a1/></a2></a3></a4> poi a1 sarà visitata 16 volte, per <a5><a4><a3><a2><a1/></a2></a3></a4></a5> - 32, ecc Quindi la complessità sembra esponenziale.

Ha senso? Come lo dimostreresti analizzando lo code?

Answer 1

Questa analisi non sarà molto rigorosa, ma il problema sembra essere il metodo di trasformazione di BasicTransformer (Seq [Node]) [1].

Il metodo di trasformazione figlio verrà chiamato due volte per un nodo che viene modificato. Nello specifico nel tuo esempio tutti i nodi verranno chiamati due volte per questo motivo. E tu hai ragione in quanto ogni nodo all'altezza h sarà chiamato 2^(h-1) volte. Si noti inoltre che al massimo un figlio di un nodo verrà chiamato due volte a causa dell'uso di span e codice, nell'esempio specifico verrà chiamato due volte il figlio dei nodi.

Solo per verificare questo ha scritto questi esempi di codice per modificato RulesTransformer. (Avrei potuto sovrascritto RulesTransformer troppo. Ma in ogni caso)

// 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 } 
    } 
} 

miei modificati 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)) 
    } 
} 

Questi codici sono solo per dimostrare scopo. È possibile chiamare questi come

new CopiedRuleTransformer(rule).apply(node) 

o

new MyRuleTransformer(rule).apply(node) 

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