- About Scala
- Documentation
- Code Examples
- Software
- Scala Developers
[scala-bts] #3689: BasicTransformer has exponential complexity
Tue, 2010-07-20, 21:20
---------------------------------+------------------------------------------
Reporter: dcsobral | Owner: scala-xml_team
Type: defect | Status: new
Priority: normal | Component: XML support
Keywords: rewriter transformer |
---------------------------------+------------------------------------------
It seems {{{BasicTransformer}}} has exponential complexity on the nesting
level of the XML being processed. This is due to this method:
{{{
def transform(ns: Seq[Node]): Seq[Node] = {
val (xs1, xs2) = ns span (n => unchanged(n, transform(n)))
if (xs2.isEmpty) ns
else xs1 ++ transform(xs2.head) ++ transform(xs2.tail)
}
}}}
Each modified node is transformed twice: once at the span, and again at
the if/else. So, for {{{}}}, with c being
modified, node a gets transformed twice, node b gets transformed four
times (twice for each time a is transformed), and node c gets transformed
eight times.
Wed, 2010-07-21, 00:17
#2
Re: [scala-bts] #3689: BasicTransformer has exponential complexi
---------------------------------+------------------------------------------
Reporter: dcsobral | Owner: scala-xml_team
Type: defect | Status: new
Priority: normal | Component: XML support
Keywords: rewriter transformer |
---------------------------------+------------------------------------------
Changes (by eengbrec):
* cc: erik.engbrecht@… (added)
---------------------------------+------------------------------------------
Reporter: dcsobral | Owner: scala-xml_team
Type: defect | Status: new
Priority: normal | Component: XML support
Keywords: rewriter transformer |
---------------------------------+------------------------------------------
Comment(by dcsobral):
I propose the following rewrite of that method as a fix:
{{{
def transform(ns: Seq[Node]): Seq[Node] = {
val xs = ns.toStream map transform
val (xs1, xs2) = xs zip ns span { case (x, n) => unchanged(n, x) }
if (xs2.isEmpty) ns
else (xs1 map (_._2)) ++ xs2.head._1 ++ transform(ns drop (xs1.length
+ 1))
}
}}}
I considered modifying {{{unchanged}}}, but, as a protected method, it is
part of the API. Also, {{{ns take xs1.length}}} might be better than
{{{xs1 map (_._2)}}}. This whole method could probably be made more
efficient with a carefully constructed while loop, I think, but this, at
least, solves the complexity problem.