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.

<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>

//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>