24 dicembre
Optimized Repetitive Prepends, Part III: Understanding the Solution
In Part II of this post a solution was given to the problem presented in Part I:
"Can we implement an algorithm for repetitive prepends that will be run by P1 in linear time, in addition to its excellent linear performance of repetitive appends?"
The solution is implemented within the function my:prepend-iter() that is defined in the following way:
|
<xsl:function name="my:prepend-iter">
<xsl:param name="pNumTimes" as="xs:integer"/>
<xsl:param name="pstartSeq" as="element()*"/>
<xsl:param name="pInserts" as="element()*"/>
<xsl:sequence select=
"if($pNumTimes gt 0)
then
my:prepend-iter
($pNumTimes -1,
$pstartSeq,
($pInserts, reverse($vPrepends) )
)
else
(reverse($pInserts), $pstartSeq)
"/>
</xsl:function> |
The first argument passed to this function, pNumTimes, is the number of times to perform the prepend operation on the initial sequence pstartSeq, which is passed as the second argument.
The third argument has an auxiliary purpose. As its name, pInserts suggests, it contains the accumulation of all sequences that are to be prepended to pstartSeq.
The idea is to produce the final result only when pNumTimes is zero, using at this time the accumulated prepends in pInserts and the initial sequence pstartSeq.
The idea of the algorithm is to replace the repetitive prepend operations with repetitive append operations, which are carried out by the xslt processor with linear complexity.
We notice that:
y2s ++ y1s ++ xs =
reverse( reverse(y1s) ++ reverse(y2s) ) ++ xs (1)
Or in general, if we have N sequences:
y1s, y2s, ..., yNs
to be prepended to an initial sequence xs in that order,
yNs ++ yN-1s ++ ... y2s ++ y1s ++ xs =
reverse(reverse(y1s)++reverse(y2s) ++ ...
... ++ reverse(yNs) ) ++xs (2)
Remarkably, the argument of the outermost reverse() is a repetitive appends operation and it has only linear complexity with P1!
We have added N+1 reverse() operations, but each of them is of linear complexity, so the total complexity of implementing (2) is O(N).
Certainly, the function my:prepend-iter() we have demonstrated is a simplified case of the many different real world scenarios we may encounter that will require repetitive prepends. Nevertheless its use is sufficient to prove and demonstrate how such an O(N) algorithm can be constructed.
We could use essentially the same algorithm, with a modification that accepts as argument a function
next-prepend(), which produces the next sequence to be prepended. To signal the end of the repetitive prepend operation, we can use a convention that next-prepend() will indicate this by producing some special sequence, such as the empty sequence.
In case you may be wondering how can a function be passed as an argument to another function in XSLT, do read about FXSL.
Strumenti 
Guida
