Einen String umkehren

(Auszug aus "XSLT Kochbuch" von Sal Mangano)

Problem

Sie müssen die Zeichen eines Strings umkehren.

Lösung

XSLT 1.0

Dieses Template kehrt $input auf raffinierte und effektive Weise um:

<xsl:template name="reverse">
  <xsl:param name="input"/>
  <xsl:variable name="len" select="string-length($input)"/>
  <xsl:choose>
    <!-- Strings mit einer Länge kleiner als 2 sind trivial umzukehren -->
    <xsl:when test="$len = 2">
      <xsl:value-of select="$input"/>
    </xsl:when>
    <!-- Strings mit der Länge 2 sind ebenfalls trivial umzukehren -->
    <xsl:when test="$len = 2">
      <xsl:value-of select="substring($input,2,1)"/>
      <xsl:value-of select="substring($input,1,1)"/>
    </xsl:when>
    <xsl:otherwise>
      <!-- Tausch der ersten Hälfte und der zweiten Hälfte der Eingabe und rekursive Anwendung dieses Templates -->
      <xsl:variable name="mid" select="floor($len div 2)"/>
      <xsl:call-template name="reverse">
        <xsl:with-param name="input" select="substring($input,$mid+1,$mid+1)"/>
      </xsl:call-template>
      <xsl:call-template name="reverse">
        <xsl:with-param name="input" select="substring($input,1,$mid)"/>
      </xsl:call-template>
    </xsl:otherwise>
  </xsl:choose>
</xsl:template>

XSLT 2.0

In 2.0 ist die Umkehrung trivial.

<xsl:function name="ckbk:reverse">
  <xsl:param name="input" as="xs:string"/>
  <xsl:sequence select="codepoints-to-string(reverse(string-to-codepoints($input)))"/>
</xsl:function>

Diskussion

XSLT 1.0

Der in der Lösung gezeigte Algorithmus ist nicht der offensichtlichste, aber er ist effizient. Um genau zu sein, kehrt dieser Algorithmus erfolgreich selbst sehr lange Strings um, während andere offensichtlichere Algorithmen entweder zu lange brauchen oder mit einem Stack-Überlauf fehlschlagen. Die grundlegende Idee hinter diesem Algorithmus besteht darin, die erste Hälfte des Strings mit der zweiten Hälfte zu tauschen und den Algorithmus so lange rekursiv auf diese Hälften anzuwenden, bis Sie nur noch Strings der Länge 2 oder kürzer haben, bei denen die Operation des Umkehrens trivial ist. Das folgende Beispiel verdeutlicht, wie dieser Algorithmus funktioniert. In jedem Schritt habe ich ein + an die Stelle gesetzt, wo der String aufgeteilt und verkettet wurde.

  1. reverse(»abcdef«) (Eingabe)
  2. reverse(def)+reverse(»abc«)
  3. reverse(»ef«) + »d« + reverse(»bc«) + »a«
  4. »f« + »e« + »d« + »c« + »b« + »a«
  5. fedcba (Ergebnis)

Das Betrachten offensichtlicherer XSLT-Implementierungen von reverse ist aufschlussreich, weil sie zeigen, wie man rekursive Lösungen in anderen Kontexten implementieren und nicht implementieren soll.

Einer der schlimmsten Algorithmen ist wahrscheinlich einer, den viele als ersten Versuch nehmen würden. Der Kern besteht darin, das erste und das letzte Zeichen des Strings zu vertauschen, dann mit dem zweiten und dem vorletzten fortzufahren usw., bis die Mitte erreicht wird, an der man fertig ist. Ein C-Programmierer könnte mit dieser Lösung ankommen, da es eine ausgesprochen effiziente, iterative Lösung für eine Sprache wie C ist, in der Sie einzelne Zeichen aus einem String zufällig lesen und schreiben können und Iteration anstelle von Rekursion die Norm ist. In XSLT jedoch müssen Sie diesen Algorithmus auf rekursive Weise implementieren, wie im folgenden Beispiel gezeigt wird, und haben nicht den Luxus, hier Variablen zu manipulieren.

Beispiel: Eine sehr schlechte Implementierung von reverse.

<xsl:template name="reverse">
  <xsl:param name="input"/>
  <xsl:variable name="len" select="string-length($input)"/>
  <xsl:choose>
    <!-- Strings mit einer Länge kleiner als 2 sind trivial umzukehren -->
    <xsl:when test="$len &lt; 2">
      <xsl:value-of select="$input"/>
    </xsl:when>
    <!-- Strings der Länge 2 sind ebenfalls trivial umzukehren -->
    <xsl:when test="$len = 2">
      <xsl:value-of select="substring($input,2,1)"/>
      <xsl:value-of select="substring($input,1,1)"/>
    </xsl:when>
    <xsl:otherwise>
      <!-- Verkettung: letztes Zeichen + reverse(mitte) + erstes Zeichen -->
      <xsl:value-of select="substring($input,$len,1)"/>
      <xsl:call-template name="reverse">
        <xsl:with-param name="input" select="substring($input,2,$len - 2)"/>
      </xsl:call-template>
      <xsl:value-of select="substring($input,1,1)"/>
    </xsl:otherwise>
  </xsl:choose>
</xsl:template>

Ein schwerwiegendes Problem bei dieser Lösung macht sie für alle bis auf sehr kurze Strings ungeeignet. Das Problem besteht darin, dass die Lösung nicht endrekursiv ist (im Absatz Endrekursion finden Sie eine entsprechende Erklärung). Viele XSLT-Prozessoren (wie etwa Saxon) sind für Endrekursion optimiert. Ihnen wird daher empfohlen, Ihren Code so zu strukturieren, dass Sie von dieser wichtigen Optimierung profitieren. Das folgende Beispiel macht diese Version von reverse endrekursiv, indem bei jedem rekursiven Aufruf nur das letzte Zeichen im String an den Anfang verschoben wird. Dies setzt den rekursiven Aufruf an das Ende und nutzt daher die Optimierung.

Beispiel: Eine ineffiziente endrekursive Implementierung.

<xsl:template name="reverse">
  <xsl:param name="input"/>
  <xsl:variable name="len" select="string-length($input)"/>
  <xsl:choose>
    <!-- Strings mit einer Länge kleiner als 2 sind trivial umzukehren -->
    <xsl:when test="$len &lt; 2">
      <xsl:value-of select="$input"/>
    </xsl:when>
    <!-- Strings der Länge 2 sind ebenfalls trivial umzukehren -->
    <xsl:when test="$len = 2">
      <xsl:value-of select="substring($input,2,1)"/>
      <xsl:value-of select="substring($input,1,1)"/>
    </xsl:when>
    <!-- Verkettung: letztes Zeichen + reverse(rest) -->
    <xsl:otherwise>
      <xsl:value-of select="substring($input,$len,1)"/>
      <xsl:call-template name="reverse">
        <xsl:with-param name="input" select="substring($input,1,$len - 1)"/>
      </xsl:call-template>
    </xsl:otherwise>
  </xsl:choose>
</xsl:template>

Diese Änderung verhindert, dass reverse einen Stack-Überlauf verursacht, ist für große Strings aber immer noch ineffizient. Beachten Sie erstens, dass jeder Schritt nur die Verschiebung eines einzigen Zeichens zur Folge hat. Zweitens muss jeder rekursive Aufruf einen String verarbeiten, der nur ein Zeichen kürzer ist als der aktuelle String. Bei sehr großen Strings überlastet dieser Aufruf potenziell das Speicherverwaltungssubsystem der XSLT-Implementierung. Bei der Bearbeitung dieses Rezepts hat Jeni Tennison darauf hingewiesen, dass eine andere Methode, die Version endrekursiv zu machen, den verbleibenden (reverse-) String und $len als Parameter an das Template übergeben würde. Dies ist im Allgemeinen eine gute Strategie, um Endrekursion zu erreichen. In diesem speziellen Fall war eine Verbesserung zu beobachten, die allerdings immer noch nicht so gut war wie die Lösung.

Ein wichtiges Ziel bei allen rekursiven Implementierungen besteht darin zu versuchen, den Algorithmus so zu strukturieren, dass jeder rekursive Aufruf ein Unterproblem aufwirft, das wenigstens halb so groß ist wie das aktuelle Problem. Dieser Ansatz sorgt dafür, dass die Rekursion schneller ausläuft. Folgt man diesem Ratschlag, erhält man die im folgenden Beispiel gezeigte Lösung für reverse.

Beispiel: Eine effiziente (aber nicht ideale) Implementierung.

<xsl:template name="reverse">
  <xsl:param name="input"/>
  <xsl:variable name="len" select="string-length($input)"/>
  <xsl:choose>
    <xsl:when test="$len &lt; 2">
      <xsl:value-of select="$input"/>
    </xsl:when>
    <xsl:otherwise>
      <xsl:variable name="mid" select="floor($len div 2)"/>
      <xsl:call-template name="reverse">
        <xsl:with-param name="input" select="substring($input,$mid+1,$mid+1)"/>
      </xsl:call-template>
      <xsl:call-template name="reverse">
        <xsl:with-param name="input" select="substring($input,1,$mid)"/>
      </xsl:call-template>
    </xsl:otherwise>
  </xsl:choose>
</xsl:template>

Diese Lösung hatte ich zuerst entwickelt. Sie funktioniert auch bei großen Strings (mehr als 1000 Zeichen) ganz gut. Sie besitzt den weiteren Vorteil, dass sie kürzer ist als die Implementierung, die im Abschnitt Lösung gezeigt wird. Der einzige Unterschied besteht darin, dass diese Implementierung nur Strings der Längen null und eins als trivial betrachtet. Die etwas schnellere Implementierung kürzt die Anzahl der rekursiven Aufrufe auf die Hälfte, indem auch Strings der Länge zwei als trivial betrachtet werden.

Alle hier gezeigten Implementierungen führen tatsächlich die gleiche Anzahl von Verkettungen durch. Ich glaube auch nicht, dass es eine Möglichkeit gibt, dies zu umgehen, ohne die Grenzen von XSLT zu verlassen. Allerdings zeigen meine Tests, dass bei einem String der Länge 1000 die beste Lösung ungefähr fünfmal schneller ist als die schlechteste. Die beste und die zweitbeste Lösung unterscheiden sich nur um den Faktor 1,3.

XSLT 2.0

Die XSLT 1.0-Lösung manipuliert den String als Teilstrings, da es keine Möglichkeit gibt, auf die Unicode-Zeichenebene zu gelangen. Die 2.0-Lösung verwendet die Funktionen string-to-codepoints und codepoints-to-string, was in den meisten 2.0-Implementierungen wahrscheinlich schneller ist, da Strings intern nur Arrays aus Unicode-Integer-Werten sind.

Endrekursion

Ein rekursiver Aufruf ist endrekursiv, wenn bei der Rückkehr des Aufrufs der zurückgegebene Wert sofort von der Funktion zurückgegeben wird. Der Begriff »End-« wird auf den rekursiven Aufruf zurückgeführt, der an das Ende kommt. Endrekursion ist wichtig, weil sie effizienter implementiert werden kann als allgemeine Rekursion. Ein allgemeiner rekursiver Aufruf muss einen neuen Stack-Rahmen etablieren, um lokale Variablen und andere Überwachungselemente abzuspeichern. Daher kann eine allgemeine rekursive Implementierung den Stack-Bereich bei großen Eingaben schnell ausschöpfen. Intern können endrekursive Implementierungen jedoch durch einen XSLT-Prozessor, der in der Lage ist, Endrekursion zu erkennen, in iterative Lösungen umgewandelt werden.

  

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