Recipe3.6.Computing Sums and Products

Recipe 3.6. Computing Sums and Products

Problem

You need to sum or multiply functions of numbers contained in a node set.

Solution

XSLT 1.0

The abstract form of sum for processors that support tail-recursive optimization is as follows:

<xsl:template name="ckbk:sum">   <!-- Initialize nodes to empty node set -->   <xsl:param name="nodes" select="/.."/>   <xsl:param name="result" select="0"/>   <xsl:choose>     <xsl:when test="not($nodes)">       <xsl:value-of select="$result"/>     </xsl:when>     <xsl:otherwise>         <!-- call or apply template that will determine value of node            unless the node is literally the value to be summed -->       <xsl:variable name="value">         <xsl:call-template name="some-function-of-a-node">           <xsl:with-param name="node" select="$nodes[1]"/>         </xsl:call-template>       </xsl:variable>        <!-- recurse to sum rest -->       <xsl:call-template name="ckbk:sum">         <xsl:with-param name="nodes" select="$nodes[position( ) != 1]"/>         <xsl:with-param name="result" select="$result + $value"/>       </xsl:call-template>     </xsl:otherwise>   </xsl:choose> </xsl:template>

Two techniques can handle a large number of nodes in the absence of tail-recursive optimization. The first is commonly called divide and conquer. The idea behind this technique is to reduce the amount of work by at least a factor of two on each recursive step:

<xsl:template name="ckbk:sum-dvc">   <xsl:param name="nodes" select="/.."/>   <xsl:param name="result" select="0"/>   <xsl:param name="dvc-threshold" select="100"/>   <xsl:choose>     <xsl:when test="count($nodes) &lt;= $dvc-threshold">         <xsl:call-template name="ckbk:sum">           <xsl:with-param name="nodes" select="$nodes"/>           <xsl:with-param name="result" select="$result"/>         </xsl:call-template>     </xsl:when>     <xsl:otherwise>       <xsl:variable name="half" select="floor(count($nodes) div 2)"/>       <xsl:variable name="sum1">         <xsl:call-template name="ckbk:sum-dvc">           <xsl:with-param name="nodes" select="$nodes[position( ) &lt;= $half]"/>          <xsl:with-param name="result" select="$result"/>           <xsl:with-param name="dvc-threshold" select="$dvc-threshold"/>         </xsl:call-template>       </xsl:variable>       <xsl:call-template name="ckbk:sum-dvc">          <xsl:with-param name="nodes" select="$nodes[position( ) > $half]"/>          <xsl:with-param name="result" select="$sum1"/>           <xsl:with-param name="dvc-threshold" select="$dvc-threshold"/>       </xsl:call-template>     </xsl:otherwise>   </xsl:choose> </xsl:template>

The second is called batching, which uses two recursive stages. The first stage divides the large problem into batches of reasonable size. The second stage processes each batch recursively:

<xsl:template name="ckbk:sum-batcher">   <xsl:param name="nodes" select="/.."/>   <xsl:param name="result" select="0"/>   <xsl:param name="batch-size" select="500"/>   <xsl:choose>     <xsl:when test="not($nodes)">       <xsl:value-of select="$result"/>     </xsl:when>     <xsl:otherwise>       <xsl:variable name="batch-sum">         <xsl:call-template name="ckbk:sum">           <xsl:with-param name="nodes"                 select="$nodes[position( ) &lt; $batch-size]"/>           <xsl:with-param name="result" select="$result"/>         </xsl:call-template>       </xsl:variable>       <xsl:call-template name="ckbk:sum-batcher">           <xsl:with-param name="nodes" select="$nodes[position( ) >= $batch-size]"/>           <xsl:with-param name="result" select="$batch-sum"/>           <xsl:with-param name="batch-size" select="$batch-size"/>       </xsl:call-template>     </xsl:otherwise>   </xsl:choose> </xsl:template>

The solutions for product are similar:

<xsl:template name="ckbk:product">   <xsl:param name="nodes" select="/.."/>   <xsl:param name="result" select="1"/>   <xsl:choose>     <xsl:when test="not($nodes)">       <xsl:value-of select="$result"/>     </xsl:when>     <xsl:otherwise>         <!-- call or apply template that will determine value of node unless the node          is literally the value to be multiplied -->       <xsl:variable name="value">         <xsl:call-template name="some-function-of-a-node">           <xsl:with-param name="node" select="$nodes[1]"/>         </xsl:call-template>       </xsl:variable>       <xsl:call-template name="ckbk:product">         <xsl:with-param name="nodes" select="$nodes[position( ) != 1]"/>         <xsl:with-param name="result" select="$result * $value"/>       </xsl:call-template>     </xsl:otherwise>   </xsl:choose> </xsl:template>     <xsl:template name="ckbk:product-batcher">   <xsl:param name="nodes" select="/.."/>   <xsl:param name="result" select="1"/>   <xsl:param name="batch-size" select="500"/>   <xsl:choose>     <xsl:when test="not($nodes)">       <xsl:value-of select="$result"/>     </xsl:when>     <xsl:otherwise>       <xsl:variable name="batch-product">         <xsl:call-template name="ckbk:product">           <xsl:with-param name="nodes" select="$nodes[position( ) &lt; $batch-size]"/>           <xsl:with-param name="result" select="$result"/>         </xsl:call-template>       </xsl:variable>       <xsl:call-template name="ckbk:product-batcher">           <xsl:with-param name="nodes" select="$nodes[position( ) >= $batch-size]"/>           <xsl:with-param name="result" select="$batch-product"/>           <xsl:with-param name="batch-size" select="$batch-size"/>       </xsl:call-template>     </xsl:otherwise>   </xsl:choose> </xsl:template>     <xsl:template name="ckbk:product-dvc">   <xsl:param name="nodes" select="/.."/>   <xsl:param name="result" select="1"/>   <xsl:param name="dvc-threshold" select="100"/>   <xsl:choose>     <xsl:when test="count($nodes) &lt;= $dvc-threshold">         <xsl:call-template name="ckbk:product">           <xsl:with-param name="nodes" select="$nodes"/>           <xsl:with-param name="result" select="$result"/>         </xsl:call-template>     </xsl:when>     <xsl:otherwise>       <xsl:variable name="half" select="floor(count($nodes) div 2)"/>       <xsl:variable name="product1">         <xsl:call-template name="ckbk:product-dvc">           <xsl:with-param name="nodes" select="$nodes[position( ) &lt;= $half]"/>          <xsl:with-param name="result" select="$result"/>           <xsl:with-param name="dvc-threshold" select="$dvc-threshold"/>         </xsl:call-template>       </xsl:variable>       <xsl:call-template name="ckbk:product-dvc">          <xsl:with-param name="nodes" select="$nodes[position( ) > $half]"/>          <xsl:with-param name="result" select="$product1"/>           <xsl:with-param name="dvc-threshold" select="$dvc-threshold"/>       </xsl:call-template>     </xsl:otherwise>   </xsl:choose> </xsl:template>

Using the built-in XPath sum( ) function is the simplest way to perform simple sums. However, if you want to compute sums of the nodes' arbitrary function in a node-set, then you need either to:

Use one of the recipes in this section.
Compute the function of the nodes first, capturing the result in a variable as a result-tree fragment. Then use an extension function to convert the fragment to a node set that can be fed to sum. In XSLT 2.0, generalized sums become trivial because of the banishment of result-tree fragments.

XSLT 2.0

Sums of arbitrary functions are trivial in 2.0 because of the introduction of sequences and the for expression and sum function in XPath:

<!--Sum of squares --> <xsl:value select="sum(for $i in $nodes return $i * $i)"/>

However, XPath does not give you a native prod( ) function, so you will need to provide your own:

<xsl:function name="ckbk:prod" as="xs:double">    <xsl:param name="numbers" as="xs:double*"/>    <xsl:sequence select="if (count($numbers) eq 0) then 0                          else if (count($numbers) = 1) then $numbers[1]                          else $numbers[1] * ckbk:prod(subsequence($numbers,2))"/>  </xsl:function>

Discussion

XSLT 1.0

Batching and divide and conquer are two techniques for managing recursion that are useful whenever you must process a potentially large set of nodes. Experimentation shows that even when using an XSLT processor that recognizes tail recursion, better performance results from these approaches.

Chapter 14 shows how to make a reusable batch and divide-and-conquer drivers.

XSLT 2.0

Given this prod function, you might be tempted use it to compute factorials:

<xsl:function name="ckbk:factorial" as="xs:double">    <xsl:param name="n" as="xs:integer"/>    <xsl:sequence select="if ($n eq 0) then 1 else ckbk:prod(1 to $n)"/>  </xsl:function>

This is probably an okay solution if $n is small, but as it gets larger, the overhead of constructing the sequence may give worse performance then the more direct solution. This is something to keep in mind when taking advantage of the convenience of sequences. Michael Kay provides other examples in discussing the differences between his Knights Tour 1.0 and 2.0 solutions (XSLT 2.0, Third Edition, Wrox, 2004, pg. 753):

//what does this code do? <xsl:function name="ckbk:factorial" as="xs:decimal">    <xsl:param name="n" as="xs:integer"/>    <xsl:sequence select="if ($n eq 0) then 1 else $n * ckbk:factorial($n - 1)"/>  </xsl:function>