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.

About these ads
This entry was posted in Performance Optimization. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s