Summen und Produkte berechnen

(Auszug aus "XSLT Kochbuch" von Sal Mangano)

Problem

Sie müssen Funktionen von Zahlen, die in einer Knotenmenge enthalten sind, summieren oder multiplizieren.

Lösung

XSLT 1.0

Für Prozessoren, die endrekursive Optimierung unterstützen, sieht die abstrakte Form von Summen folgendermaßen aus:

<xsl:template name="ckbk:sum">
  <!-- Knoten auf eine leere Knotenmenge initialisieren -->
  <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>
      <!-- Template aufrufen oder anwenden, das den Wert des Knotens ermittelt, es sei denn,der Knoten ist der tatsächliche Wert, der summiert werden soll -->
      <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>
      <!-- Rekursion, um den Rest zu summieren -->
      <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>

Beim Fehlen einer endrekursiven Optimierung gibt es zwei Techniken, die mit einer großen Anzahl von Knoten umgehen können. Die erste wird üblicherweise teile und herrsche genannt. Der Grundgedanke hinter dieser Technik besteht darin, bei jedem rekursiven Schritt die Menge der zu verrichtenden Arbeit um wenigstens den Faktor zwei zu verringern:

<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( ) &gt; $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>

Die zweite wird als Batching (Stapelung) bezeichnet und verwendet zwei rekursive Stufen. Die erste Stufe teilt das große Problem in Stapel vernünftiger Größe auf. Die zweite Stufe verarbeitet die einzelnen Stapel rekursiv:

<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( ) &gt;= $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>

Die Lösungen für product sehen ähnlich aus:

<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>
      <!-- Template aufrufen oder anwenden, das den Wert des Knotens ermittelt, es sei denn, der Knoten ist tatsächlich der Wert, der multipliziert werden soll -->
      <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( ) &gt;= $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( ) &gt; $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>

Anmerkung:
Die Anwendung der integrierten XPath-Funktion sum( ) ist die einfachste Möglichkeit, einfache Summen auszuführen. Falls Sie jedoch die Summen einer beliebigen Funktion der Knoten in einer Knotenmenge berechnen wollen, müssen Sie entweder

  • eines der Rezepte in diesem Abschnitt anwenden oder
  • die Funktion der Knoten zuerst berechnen und das Ergebnis in einer Variablen als Ergebnisbaumfragment erfassen. Dann setzen Sie eine Erweiterungsfunktion ein, um das Fragment in eine Knotenmenge umzuwandeln, die an sum übergeben werden kann. In XSLT 2.0 werden verallgemeinerte Summen trivial, da Ergebnisbaumfragmente nicht mehr erlaubt sind.

XSLT 2.0

In 2.0 sind Summen beliebiger Funktionen aufgrund der Einführung von Sequenzen sowie des for-Ausdrucks und der sum-Funktion in XPath trivial:

<!-- Summe von Quadraten --> 
<xsl:value select="sum(for $i in $nodes return $i * $i)"/>

Allerdings bietet Ihnen XPath keine native prod( )-Funktion, sodass Sie Ihre eigene anbieten müssen:

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

Diskussion

XSLT 1.0

Batching und Teile-und-herrsche sind zwei Techniken zur Verwaltung von Rekursionen, die immer dann nützlich sind, wenn Sie eine potenziell große Menge von Knoten verarbeiten müssen. Versuche zeigen, dass diese Ansätze sogar dann eine bessere Leistungsfähigkeit bieten, wenn Sie einen XSLT-Prozessor verwenden, der Endrekursion erkennt.

Tipp: XSLT erweitern und einbetten zeigt, wie Sie wiederverwendbare Batch- und Teile-und-herrsche-Treiber herstellen.

XSLT 2.0

Sie könnten versucht sein, auf der Grundlage dieser Produktfunktion Fakultäten zu berechnen:

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

Das ist wahrscheinlich eine annehmbare Lösung, wenn $n klein ist. Wird es jedoch größer, ergibt sich aus dem Aufwand für die Konstruktion der Sequenz möglicherweise eine schlechtere Leistung als bei der direkteren Lösung. Dies sollten Sie bedenken, wenn Sie die Bequemlichkeit von Sequenzen ausnutzen. Michael Kay bietet weitere Beispiele bei der Diskussion der Unterschiede zwischen seinen Knights-Tour-1.0- und −2.0-Lösungen (XSLT 2.0, Dritte Auflage, Wrox, 2004, S. 753):

//was tut dieser Code?
<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>

  

<< zurück vor >>

 

 

 

Tipp der data2type-Redaktion:
Zum Thema XSLT bieten wir auch folgende Schulungen zur Vertiefung und professionellen Fortbildung an:

Copyright © 2006 O'Reilly Verlag GmbH & Co. KG
Für Ihren privaten Gebrauch dürfen Sie die Online-Version ausdrucken.
Ansonsten unterliegt dieses Kapitel aus dem Buch "XSLT Kochbuch" denselben Bestimmungen, wie die gebundene Ausgabe: Das Werk einschließlich aller seiner Teile ist urheberrechtlich geschützt. Alle Rechte vorbehalten einschließlich der Vervielfältigung, Übersetzung, Mikroverfilmung sowie Einspeicherung und Verarbeitung in elektronischen Systemen.

O'Reilly Verlag GmbH & Co. KG, Balthasarstraße 81, 50670 Köln, kommentar(at)oreilly.de