scala.xml.RuleTransformer की जटिलता वास्तव में घातीय है?

Question

यह मेरी पिछली पोस्ट के one पर एक फॉलो-अप है।

मैंने यह समझने की कोशिश की कि RuleTransformer प्रदर्शन इतना खराब क्यों है। अब मुझे विश्वास है कि यह बहुत धीमा है क्योंकि इसकी जटिलता ओ (2 ^एन) है, जहां एन इनपुट एक्सएमएल पेड़ की ऊंचाई है।

मान लीजिए मैं लेबल करने के लिए "बी" सभी तत्वों के सभी लेबल का नाम बदलने की जरूरत है:

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 
} 

अब यह आरईपीएल में चलाते हैं और देखते हैं 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 के लिए <a5><a4><a3><a2><a1/></a2></a3></a4></a5> 16 बार, का दौरा किया जाएगा -, 32 आदि तो जटिलता घातीय लग रहा है।

क्या यह समझ में आता है? code के विश्लेषण से आप इसे कैसे साबित करेंगे?

Answer 1

यह बहुत कठोर विश्लेषण नहीं होगा, लेकिन समस्या बेसिकट्रांसफॉर्मर के ट्रांसफॉर्म (सेक [नोड]) विधि [1] के साथ प्रतीत होती है।

बाल परिवर्तन विधि को नोड के लिए दो बार बुलाया जाएगा जो बदला जाता है। विशेष रूप से आपके उदाहरण में सभी कारणों को इस कारण से दो बार बुलाया जाएगा। और आप सही हैं कि प्रत्येक नोड ऊंचाई ऊंचाई पर 2^(एच -1) बार कहा जाएगा। यह भी ध्यान रखें कि नोड के अधिकांश बच्चे को दो बार बुलाया जाएगा क्योंकि स्पैन और कोड का उपयोग, विशिष्ट उदाहरण में नोड्स के सभी बच्चे को दो बार बुलाया जाएगा।

बस यह सत्यापित करने के लिए कि संशोधित नियम ट्रांसफॉर्मर के लिए इन कोड नमूने लिखे गए हैं। (मैं ओवरराइड किया जा सकता था 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