Maxima und Minima ermitteln

(Auszug aus "XSLT Kochbuch" von Sal Mangano)

Problem

Sie müssen den (oder die) kleinsten (oder größten) numerischen Knoten in einer Knotenmenge finden.

Lösung

XSLT 1.0

Die EXSLT-Funktionen, die diese Operationen ausführen, sind exsl:min, exsl:max, exsl:lowest und exsl:highest. Die Funktionen min und max ermitteln den Wert des Knotens mit dem minimalen bzw. maximalen numerischen Wert. EXSLT definiert exsl:min so, wie es hier aufgeführt ist:

  • Der Minimalwert wird folgendermaßen definiert: Die Knotenmenge, die als Argument übergeben wurde, wird in aufsteigender Reihenfolge sortiert, wie dies durch xsl:sort mit dem Datentyp number geschehen würde. Das Minimum ist das Ergebnis der Konvertierung des Stringwertes des ersten Knotens in dieser sortierten Liste mit Hilfe der Funktion number in eine Zahl.
  • Wenn die Knotenmenge leer ist oder wenn das Ergebnis der Konvertierung der Stringwerte irgendeines der Knoten in eine Zahl NaN ist, dann wird NaN zurückgeliefert.

exsl:max wird ähnlich definiert. EXSLT bietet reine XSLT-Implementierungen, die wörtliche Implementierungen dieser Definition sind, wie im folgendne Beispiel gezeigt.

Beispiel: EXSLT-min und -max, direkt aus der Definition implementiert.

<xsl:template name="ckbk:min">
  <xsl:param name="nodes" select="/.." />
  <xsl:choose>
    <xsl:when test="not($nodes)">NaN</xsl:when>
    <xsl:otherwise>
      <xsl:for-each select="$nodes">
        <xsl:sort data-type="number" />
        <xsl:if test="position() = 1">
          <xsl:value-of select="number(.)" />
        </xsl:if>
      </xsl:for-each>
    </xsl:otherwise>
  </xsl:choose>
</xsl:template>
<xsl:template name="ckbk:max">
  <xsl:param name="nodes" select="/.." />
  <xsl:choose>
    <xsl:when test="not($nodes)">NaN</xsl:when>
    <xsl:otherwise>
      <xsl:for-each select="$nodes">
        <xsl:sort data-type="number" order="descending" />
        <xsl:if test="position() = 1">
          <xsl:value-of select="number(.)" />
        </xsl:if>
      </xsl:for-each>
    </xsl:otherwise>
  </xsl:choose>
</xsl:template>

Sie werden sich vielleicht wegen des Vorgabewertes für den nodes-Parameter an den Kopf fassen (select="/ .. "). Dies ist einfach eine idiomatische Methode, um Knoten auf eine leere Knotenmenge zu initialisieren (d. h. der Elternknoten der Wurzel ist laut Definition leer).

Die Definitionen von ckbk:min und ckbk:max benutzen zwar xsl:sort, die Implementierungen jedoch müssen es nicht, so dass Ergebnisse möglich sind, die effektiver ausfallen, vorausgesetzt, Ihr XSLT-Prozessor unterstützt Endrekursion (siehe folgendes Beispiel).

Beispiel: min und max, implementiert mit Teile-und-herrsche.

<xsl:template name="ckbk:max">
  <xsl:param name="nodes" select="/.."/>
  <xsl:param name="max"/>
  <xsl:variable name="count" select="count($nodes)"/>
  <xsl:variable name="aNode" select="$nodes[ceiling($count div 2)]"/>
  <xsl:choose>
    <xsl:when test="not($count)">
      <xsl:value-of select="number($max)"/>
    </xsl:when>
    <xsl:when test="number($aNode) != number($aNode)">
      <xsl:value-of select="number($aNode)"/>
    </xsl:when>
    <xsl:otherwise>
      <xsl:call-template name="ckbk:max">
        <xsl:with-param name="nodes" select="$nodes[not(. <= number($aNode))]"/>
        <xsl:with-param name="max">
          <xsl:choose>
            <xsl:when test="not($max) or $aNode &gt; $max">
              <xsl:value-of select="$aNode"/>
            </xsl:when>
            <xsl:otherwise>
              <xsl:value-of select="$max"/>
            </xsl:otherwise>
          </xsl:choose>
        </xsl:with-param>
      </xsl:call-template>
    </xsl:otherwise>
  </xsl:choose>
</xsl:template>
<xsl:template name="ckbk:min">
  <xsl:param name="nodes" select="/.."/>
  <xsl:param name="min"/>
  <xsl:variable name="count" select="count($nodes)"/>
  <xsl:variable name="aNode" select="$nodes[ceiling($count div 2)]"/>
  <xsl:choose>
    <xsl:when test="not($count)">
      <xsl:value-of select="number($min)"/>
    </xsl:when>
    <xsl:when test="number($aNode) != number($aNode)">
      <xsl:value-of select="number($aNode)"/>
    </xsl:when>
    <xsl:otherwise>
      <xsl:call-template name="ckbk:min">
        <xsl:with-param name="nodes" select="$nodes[not(. &gt;= number($aNode))]"/>
        <xsl:with-param name="min">
          <xsl:choose>
            <xsl:when test="not($min) or $aNode &lt; $min">
              <xsl:value-of select="$aNode"/>
            </xsl:when>
            <xsl:otherwise>
              <xsl:value-of select="$min"/>
            </xsl:otherwise>
          </xsl:choose>
        </xsl:with-param>
      </xsl:call-template>
    </xsl:otherwise>
  </xsl:choose>
</xsl:template>

Typischerweise sind die gezeigten Implementierungen schneller als die Versionen, die xsl:sort benutzen. In einigen seltsamen Fällen kann es vorkommen, dass sie langsamer sind. Der Grund dafür liegt darin, dass die Effizienz davon abhängig ist, dass bei jedem rekursiven Schritt (durchschnittlich) die Hälfte der Knoten aus dem Blickfeld entfernt wird. Man kann sich ein Szenario vorstellen, in dem bei jedem Durchlauf aNode der verbleibende Minimumknoten (im Fall von ckbk:max) oder der Maximumknoten (im Fall von ckbk:min) ist. Würde dies geschehen, dann würde bei jedem Durchlauf immer nur ein Knoten entfernt werden, was eine schlechte Leistungsfähigkeit zur Folge hätte. Glücklicherweise kommen die Daten meist in zwei Konfigurationen: vorsortiert und zufällig. In beiden Fällen sollten diese Implementierungen funktionieren.

Sie mussten noch ausdrücklich nach nicht-numerischen Daten Ausschau halten. Die EXSLT-Implementierungen überlassen diese Sorge xsl:sort. Der XSLT-Standard verlangt, dass nicht-numerische Daten bei der Sortierung nach vorn gestellt werden, wenn data-type='number' lautet.

Achtung!
Versuchen Sie gar nicht erst, not(number($var)) zu schreiben, um auf NaN zu testen! Ich erwische mich oft dabei, weil das so korrekt klingt. Die number-Funktion testet nicht auf eine Zahl, sondern versucht stattdessen, ihr Argument in eine Zahl umzuwandeln. Das wollen Sie ganz bestimmt nicht – dieser Test geht nämlich wegen der Konvertierung von 0 in false davon aus, dass 0 keine Zahl ist. Der richtige Test lautet number($var) != number($var). Dieser Test funktioniert, weil NaN niemals gleich NaN, aber eine beliebige Zahl immer gleich sie selbst ist. Lassen Sie sich nicht dazu hinreißen, dieses Idiom zu number($var) != $var abzukürzen. Das funktioniert zwar meist; falls $var jedoch eine leere Knotenmenge ist, schlägt es fehl. Wenn es Ihnen lieber ist, nehmen Sie einen direkteren Ansatz: string(number($var)) = 'NaN' funktioniert.

EXSLT definiert ckbk:lowest folgendermaßen:

  • Die Funktion ckbk:lowest liefert die Knoten in der Knotenmenge zurück, deren Wert der Minimalwert für die Knotenmenge ist. Der Minimalwert für die Knotenmenge ist identisch mit dem Wert, der von ckbk:min berechnet wurde. Ein Knoten besitzt diesen Minimalwert, wenn das Ergebnis der Konvertierung seines Stringwertes in eine Zahl, wie durch die Funktion number, gleich dem Minimalwert ist, wobei der Gleichheitsvergleich als numerischer Vergleich mit Hilfe des Operators = definiert ist.
  • Falls einer der Knoten in der Knotenmenge einen nicht-numerischen Wert hat, liefert die Funktion ckbk:min das Ergebnis NaN. Die Definition numerischer Vergleiche besagt, dass NaN != NaN. Besitzt daher einer der Knoten in der Knotenmenge einen nicht-numerischen Wert, liefert ckbk:lowest eine leere Knotenmenge.

Die EXSLT-Implementierung basiert wörtlich auf dieser Definition und ist möglicherweise nicht sehr effizient:

<xsl:template name="ckbk:lowest">
  <xsl:param name="nodes" select="/.." />
  <xsl:if test="$nodes and not($nodes[number(.) != number(.)])">
    <xsl:variable name="min">
      <xsl:for-each select="$nodes">
        <xsl:sort data-type="number" />
        <xsl:if test="position( ) = 1">
          <xsl:value-of select="number(.)" />
        </xsl:if>
      </xsl:for-each>
    </xsl:variable>
    <xsl:copy-of select="$nodes[. = $min]" />
  </xsl:if>
</xsl:template>

Der xsl:if-Test überprüft alle Knoten, um Fälle zu bewältigen, bei denen ein nicht-numerischer Wert vorhanden ist. Anschließend sortiert er, um min zu ermitteln, und sammelt schließlich alle Knoten mit diesem min. Das folgende Beispiel verwendet ebenfalls ckbk:min, um dieselbe Aktion auszuführen, ohne extra sortieren zu müssen.

Beispiel: Lowest, ebenfalls mit Hilfe von ckbk:min implementiert.

<xsl:template name="ckbk:lowest">
  <xsl:param name="nodes" select="/.."/>
  <xsl:variable name="min">
    <xsl:call-template name="ckbk:min">
      <xsl:with-param name="nodes" select="$nodes"/>
    </xsl:call-template>
  </xsl:variable>
  <xsl:choose>
    <xsl:when test="number($min) = number($min)">
      <xsl:copy-of select="$nodes[. = $min]"/>
    </xsl:when>
  </xsl:choose>
</xsl:template>

Schließlich können Sie ckbk:lowest mit nur einem einzigen Durchlauf über die Knoten implementieren, falls Sie auf die erneute Verwendung von ckbk:min verzichten wollen (siehe folgendes Beispiel).

Beispiel: Lowest, implementiert ohne erneute Verwendung von ckbk:min.

<xsl:template name="ckbk:lowest">
  <xsl:param name="nodes" select="/.."/>
  <xsl:param name="lowest" select="/.."/>
  <xsl:variable name="index" select="ceiling(count($nodes) div 2)"/>
  <xsl:variable name="aNode" select="$nodes[$index]"/>
  <xsl:choose>
    <xsl:when test="not($index)">
      <xsl:copy-of select="$lowest"/>
    </xsl:when>
    <xsl:when test="number($aNode) != number($aNode)"/>
    <xsl:otherwise>
      <xsl:choose>
        <xsl:when test="not($lowest) or $aNode &lt; $lowest">
          <xsl:call-template name="ckbk:lowest">
            <xsl:with-param name="nodes" select="$nodes[not(. &gt;= $aNode)]"/>
            <xsl:with-param name="lowest" select="$nodes[. = $aNode]"/>
          </xsl:call-template>
        </xsl:when>
        <xsl:when test="$aNode = $lowest">
          <xsl:call-template name="ckbk:lowest">
            <xsl:with-param name="nodes" select="$nodes[not(. &gt;= $aNode)]"/>
            <xsl:with-param name="lowest" select="$lowest|$nodes[$index]"/>
          </xsl:call-template>
        </xsl:when>
        <xsl:otherwise>
          <xsl:call-template name="ckbk:lowest">
            <xsl:with-param name="nodes" select="$nodes[not(. &gt;= $aNode)]"/>
            <xsl:with-param name="lowest" select="$lowest"/>
          </xsl:call-template>
        </xsl:otherwise>
      </xsl:choose>
    </xsl:otherwise>
  </xsl:choose>
</xsl:template>

Interessanterweise ist diese Implementierung schlechter, möglicherweise wegen des zusätzlichen Kopierens. Bei einem Leistungstest mit 10.000 Datenpunkten, die verschiedene Datenverteilungen aufwiesen (sortiert, rückwärts sortiert, halbzufällig und zufällig), schug die ckbk:min-basierte Implementierung die xsl:sort-basierte Implementierung um durchschnittlich etwa 40% (oft mehr). Die rekursive Implementierung ohne ckbk:min war 24% langsamer als diejenige mit dieser Funktion.

Die ckbk:highest-Definition und -Implementierungen folgen direkt aus dem Umkehren der relationalen Logik von ckbk:lowest, weshalb ich sie hier nicht noch einmal erläutere.

XSLT 2.0

XPath 2.0 besitzt eigene min- und max-Funktionen.

Diskussion

Die Minimal- und Maximalwerte einer Knotenmenge können durch die einfachen XPath-Ausdrücke <xsl:value-of select="$nodes[not($nodes < .)]"/> und <xsl:value-of select="$nodes[not($nodes > .)]"/> ermittelt werden. Der erste Ausdruck besagt: »Wähle alle Knoten, für die es keinen Knoten gibt, der kleiner ist als dieser Wert«, und der zweite besagt: »Wähle alle Knoten, für die es keinen Knoten gibt, der größer ist als dieser Wert«.

Obwohl diese Ausdrücke sehr einfach sind, haben sie die Leistung O(N2), wobei N die Anzahl der Knoten ist. Sie sollten diese Kurzform daher nach Möglichkeit vermeiden, es sei denn, Sie sind sich sicher, dass die Anzahl der Knoten klein ist. Manchmal sind Sie gezwungen, sie zu verwenden, weil Sie beispielsweise min/max innerhalb des select-Attributs von xsl:sort oder des use-Attributs von xsl:key finden müssen (wofür Sie kein Template aufrufen können).

In einer anderen XSLT-Publikation wurde die folgende rekursive Implementierung zum Ermitteln von Minima als effizienter als diejenige mit xsl:sort beschrieben:

<xsl:template name="ckbk:min">
  <xsl:param name="nodes" select="/.."/>
  <xsl:param name="min" select="number('NaN')"/>
  <xsl:choose>
    <xsl:when test="not($nodes)">
      <xsl:value-of select="number($min)"/>
    </xsl:when>
    <xsl:otherwise>
      <xsl:variable name="aNode" select="$nodes[1]"/>
      <xsl:call-template name="ckbk:min">
        <xsl:with-param name="nodes" select="$nodes[position( ) &gt; 1]"/>
        <xsl:with-param name="min">
          <xsl:choose>
            <xsl:when test="$aNode &lt; $min or string($min) = 'NaN'">
              <xsl:value-of select="$aNode"/>
            </xsl:when>
            <xsl:otherwise>
              <xsl:value-of select="$min"/>
            </xsl:otherwise>
          </xsl:choose>
        </xsl:with-param>
      </xsl:call-template>
    </xsl:otherwise>
  </xsl:choose>
</xsl:template>

Auf keiner der XSLT-Implementierungen, die ich getestet habe, ist dies der Fall, und ich kann mir auch nicht vorstellen, dass es jemals so sein wird. Wahrscheinlich wird es sogar langsamer sein, weil bei jedem Schritt nur ein Knoten aus der Betrachtung entfernt wird. Selbst mit Endrekursion müssen Knoten oft kopiert werden. Es ist einfach, fälschlicherweise anzunehmen, dass diese rekursive Lösung so effizient ist wie die Lösung mittels iterativer Indizierung, die Sie in C oder Java finden könnten. Allerdings ist Indizierung nicht dasselbe wie das Erzeugen einer brandneuen Knotenmenge durch das Entfernen des ersten Elements, wie es mit $nodes[position( ) > 1] geschieht.

Wenn Sie das Minimum einer Datenmenge ermitteln müssen, dann müssen Sie häufig auch das Maximum finden. Es wäre schön, eine Funktion zu haben, die Ihnen zwei Ergebnisse zum Preis von einem liefert. Folgender Code erledigt das bei nur geringfügig höherer Komplexität:

<xsl:template name="ckbk:min-max">
  <xsl:param name="nodes" select="/.."/>
  <xsl:param name="nodes-for-max" select="$nodes"/>
  <xsl:param name="min"/>
  <xsl:param name="max"/>
  <xsl:variable name="count1" select="count($nodes)"/>
  <xsl:variable name="aNode1" select="$nodes[ceiling($count1 div 2)]"/>
  <xsl:variable name="count2" select="count($nodes-for-max)"/>
  <xsl:variable name="aNode2" select="$nodes-for-max[ceiling($count2 div 2)]"/>
  <xsl:choose>
    <xsl:when test="not($count1) and not($count2)">
      <xsl:value-of select="concat(number($min),',',number($max))"/>
    </xsl:when>
    <xsl:when test="number($aNode1) != number($aNode1) and number($aNode2) != number($aNode2)">
      <xsl:value-of select="concat(number($aNode1),',',number($aNode2))"/>
    </xsl:when>
    <xsl:otherwise>
      <xsl:call-template name="ckbk:min-max">
        <xsl:with-param name="nodes" select="$nodes[not(. &gt;= number($aNode1))]"/>
        <xsl:with-param name="nodes-for-max" select="$nodes-for-max[not(. &lt;= number($aNode2))]"/>
        <xsl:with-param name="min">
          <xsl:choose>
            <xsl:when test="not($min) or $aNode1 &lt; $min">
              <xsl:value-of select="$aNode1"/>
            </xsl:when>
            <xsl:otherwise>
              <xsl:value-of select="$min"/>
            </xsl:otherwise>
          </xsl:choose>
        </xsl:with-param>
        <xsl:with-param name="max">
          <xsl:choose>
            <xsl:when test="not($max) or $aNode2 &gt; $max">
              <xsl:value-of select="$aNode2"/>
            </xsl:when>
            <xsl:otherwise>
              <xsl:value-of select="$max"/>
            </xsl:otherwise>
          </xsl:choose>
        </xsl:with-param>
      </xsl:call-template>
    </xsl:otherwise>
  </xsl:choose>
</xsl:template>

Tests zeigen, dass dieser Ansatz die auf Sortierung basierende Lösung ebenfalls übertrifft.

Beim Betrachten von Minima und Maxima wurde nur ein Sonderfall beachtet: Wenn die Knoten tatsächlich die Zahlen sind, die Sie verarbeiten müssen. Ein allgemeineres Problem betrifft das Ermitteln des Minimums oder Maximums einer Funktion der Knoten in einer Knotenmenge. Nehmen Sie beispielsweise an, dass Sie eine Menge von positiven und negativen Zahlen haben und das Minimum des Quadrats ihres Wertes benötigen. Es ist zwar einfach, die gezeigten Implementierungen entsprechend so zu verändern, dass sie das Quadrieren übernehmen, allerdings ist eine einzelne wiederverwendbare Implementierung erstrebenswerter. XSLT erweitern und einbetten nimmt sich dieses Problems erneut an und beschreibt mehrere Alternativen zum Schaffen generischer Lösungen.

  

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