0

我正在尝试使用 XSLT 编写堆排序算法。但是努力交换用于存储标记化值的变量的值。我创建了方法 heapify 用于比较值并将较大的值交换为当前索引。请任何人帮助指导我交换父列表的值。

<xsl:template match="/">

      <xsl:variable name="tokenizedSample" select="tokenize(.,' ')">             
    </xsl:variable>
    <!--<xsl:value-of select="."/>-->
    <xsl:call-template name="BuildHeap">
      <xsl:with-param name="intList" select="$tokenizedSample"/>
    </xsl:call-template>
  </xsl:template>



  <xsl:template name="BuildHeap">
   <xsl:param name="intList"/>
      <xsl:for-each select="$intList">
        <xsl:call-template name="Heapify">
          <xsl:with-param name="newintList" select="$intList"/>
          <xsl:with-param name="index"  select="position()"/>
        </xsl:call-template>
      </xsl:for-each>
 </xsl:template>



  <xsl:template name="Heapify">    
    <xsl:param name="newintList"/>
    <xsl:param name="index"/>
    <xsl:variable name="stringval">
      <xsl:text></xsl:text>
    </xsl:variable>
    <xsl:variable name="vIndex">
      <xsl:number value="$index" />
    </xsl:variable>

    <xsl:variable name="stringval" select="concat(($stringval),'is')"/>
    <xsl:if test="$newintList[$vIndex*2] &gt; $newintList[$vIndex*1]  and $newintList[$vIndex*2] &gt; $newintList[($vIndex*2)+1] ">

    <!—swap the values of ith position with 2ith position-->

      <xsl:for-each select="$newintList">
        <xsl:if test="position()=$vIndex">
          <xsl:value-of select="$newintList[$vIndex*2]"/>
          <xsl:value-of select="$stringval"/>
          <xsl:variable name="stringval" select="concat(($stringval),'is',$newintList[$vIndex*2])"/>
          <xsl:value-of select="$stringval"/>
        </xsl:if>

        <xsl:if test="position()=($vIndex*2)">
          <xsl:value-of select="$stringval"/>
          <xsl:variable name="stringval" select="concat(($stringval),'is')"/>
          <xsl:value-of select="$stringval"/>
          <xsl:variable name="stringval" select="concat(($stringval),'is',$newintList[$vIndex*1])"/>
        </xsl:if>

      </xsl:for-each>

<xsl:value-of select="$stringval"/>
    </xsl:if>


    <xsl:if test="$newintList[($vIndex*2)+1] &gt; $newintList[$vIndex*1]  and $newintList[($vIndex*2)+1] &gt; $newintList[$vIndex*2] ">
    <!—swap the values of ith position with 2i+1th position-->

    </xsl:if>

  </xsl:template>
4

2 回答 2

1

I. 这是一个 XSLT 2.0 解决方案：

<xsl:stylesheet version="2.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
 xmlns:my="my:my" xmlns:xs="http://www.w3.org/2001/XMLSchema">
 <xsl:output omit-xml-declaration="yes" indent="yes"/>

 <xsl:template match="/">
  <xsl:sequence select="my:swap(/*/*, 3, 7)"/>
 </xsl:template>

 <xsl:function name="my:swap" as="item()*">
  <xsl:param name="pSeq" as="item()*"/>
  <xsl:param name="pPos1" as="xs:integer"/>
  <xsl:param name="pPos2" as="xs:integer"/>

  <xsl:sequence select=
   "$pSeq[position() lt $pPos1],
    $pSeq[$pPos2],
    $pSeq[position() gt $pPos1 and position() lt $pPos2],
    $pSeq[$pPos1],
    $pSeq[position() gt $pPos2]
   "/>
 </xsl:function>
</xsl:stylesheet>

当此转换应用于以下 XML 文档时：

<nums>
  <num>01</num>
  <num>02</num>
  <num>03</num>
  <num>04</num>
  <num>05</num>
  <num>06</num>
  <num>07</num>
  <num>08</num>
  <num>09</num>
  <num>10</num>
</nums>

产生了想要的正确结果：

<num>01</num>
<num>02</num>
<num>07</num>
<num>04</num>
<num>05</num>
<num>06</num>
<num>03</num>
<num>08</num>
<num>09</num>
<num>10</num>

二、等效的 XSLT 1.0 解决方案：

<xsl:stylesheet version="1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
 <xsl:output omit-xml-declaration="yes" indent="yes"/>

 <xsl:template match="/">
  <xsl:call-template name="swap">
   <xsl:with-param name="pSeq" select="/*/*"/>
   <xsl:with-param name="pPos1" select="3"/>
   <xsl:with-param name="pPos2" select="7"/>
  </xsl:call-template>
 </xsl:template>

 <xsl:template name="swap">
  <xsl:param name="pSeq"/>
  <xsl:param name="pPos1"/>
  <xsl:param name="pPos2"/>

  <xsl:copy-of select="$pSeq[$pPos1 > position()]"/>
  <xsl:copy-of select="$pSeq[$pPos2]"/>
  <xsl:copy-of select="$pSeq[position() > $pPos1 and $pPos2 > position()]"/>
  <xsl:copy-of select="$pSeq[$pPos1]"/>
  <xsl:copy-of select="$pSeq[position() > $pPos2]"/>
 </xsl:template>
</xsl:stylesheet>

当此转换应用于同一个 XML 文档（如上）时，会产生相同的正确结果：

<num>01</num>
<num>02</num>
<num>07</num>
<num>04</num>
<num>05</num>
<num>06</num>
<num>03</num>
<num>08</num>
<num>09</num>
<num>10</num>
于 2012-11-19T01:18:15.057 回答
0

这是 Dimitre 的 XSLT 2.0 解决方案的一个调整。它在规模上效率不高，但有些人可能更喜欢提高的可读性

将 xsl:sequence 指令修改为...

  <xsl:sequence select="
    for $i in $pSeq,
        $p in index-of( $pSeq, $i) return
      $pSeq[
           if ($p eq $pPos1) then
               $pPos2
           else if ($p eq $pPos2) then
               $pPos1
           else
               $p]" />
   </xsl:function>

警告：

为此，它需要 $pSeq 完全由独特的项目组成。如果序列包含重复节点或相同值的原子项，它将不起作用。但是从问题的上下文来看，这可能是一个安全的假设。

更新：

这是一个更好的。

  <xsl:sequence select="
    for $p in 1 to count($pSeq) return
      $pSeq[
           if ($p eq $pPos1) then
               $pPos2
           else if ($p eq $pPos2) then
               $pPos1
           else
               $p]" />
   </xsl:function>

更新#2

Dimitre 和我自己对 OP 问题的解决方案都是绝对正确的。OP已经回答说他的答案以某种方式没有给出想要的结果？但一直无法阐明与此结果错误有关的任何相关细节。很难帮助不愿意澄清的发帖者，所以我认为我在这里能做的最有帮助的事情就是为 OP 正在尝试开发的 HeapSort 提供一个完整的解决方案。

正如其他人所说，在现实环境中，只需使用 xsl:sort。事实上，即使作为一个学术问题，它也不是一个好的学术问题，因为它与现实世界的解决方案有必要的距离，很可能会误导和混淆学生。不过，我向您展示了 Heapsort 的 XSLT 2.0 实现（使用此维基百科页面上的算法）。

（更新说明）

请参阅 Dimitre 关于效率的评论。与本机排序 (xsl:sort) 相比，任何自定义构建的排序都将非常低效。确实没有充分的理由这样做，除非作为学术活动被迫这样做。

由于 OP 忘记提供用例，我将在这里提供一个。

用例 1：

有了这个输入...

<t>6 5 3 1 8 7 2 4</t>

目标是对整数进行排序并产生这个输出......

<t>
   <n>1</n>
   <n>2</n>
   <n>3</n>
   <n>4</n>
   <n>5</n>
   <n>6</n>
   <n>7</n>
   <n>8</n>
</t>

此 XSLT 2.0 样式表将使用堆排序算法对整数数组进行排序...

（更新说明）

此样式表中有错误。我正在纠正它。

<xsl:stylesheet version="2.0"
  xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
  xmlns:xs="http://www.w3.org/2001/XMLSchema"
  xmlns:fn="http://www.w3.org/2005/xpath-functions"
  xmlns:so="http://stackoverflow.com/questions/13445906"
  exclude-result-prefixes="xsl xs fn so">
<xsl:output omit-xml-declaration="yes" indent="yes" />

<xsl:template match="/*">
  <xsl:copy>
    <xsl:for-each select="so:heapsort( for $x in tokenize(.,' ') return xs:integer($x))">
      <n><xsl:value-of select="." /></n>
    </xsl:for-each>
  </xsl:copy>   
</xsl:template>

<xsl:function name="so:heapsort" as="xs:integer*">
  <xsl:param name="a" as="xs:integer*" />
  <xsl:sequence select="so:one-heapsort( so:heapify( $a, count($a) idiv 2), count($a))" />
</xsl:function>

<xsl:function name="so:one-heapsort" as="xs:integer*">
  <xsl:param name="a" as="xs:integer*" />
  <xsl:param name="end" as="xs:integer" />
  <xsl:choose>
    <xsl:when test="$end gt 0">
      <xsl:sequence select="so:one-heapsort(
        so:siftDown( so:swap( $a, 1, $end), 1, $end - 1),
        $end - 1)" />
    </xsl:when>
    <xsl:otherwise>
      <xsl:sequence select="$a" />
    </xsl:otherwise>
  </xsl:choose>
</xsl:function>

<xsl:function name="so:heapify" as="xs:integer*">
  <xsl:param name="a" as="xs:integer*" />
  <xsl:param name="start" as="xs:integer" />
  <xsl:choose>
    <xsl:when test="$start gt 0">
      <xsl:sequence select="so:heapify(
        so:siftDown( $a, $start, count($a)),
        $start - 1)" />
    </xsl:when>
    <xsl:otherwise>
      <xsl:sequence select="$a" />
    </xsl:otherwise>
  </xsl:choose>
</xsl:function>

<xsl:function name="so:siftDown" as="xs:integer*">
  <xsl:param name="a" as="xs:integer*" />
  <xsl:param name="start" as="xs:integer" />
  <xsl:param name="end" as="xs:integer" />

  <xsl:sequence select="
    subsequence( $a, 1, $start - 1),
    so:one-siftDown( subsequence( $a, $start, $end - $start + 1), 1),
    subsequence( $a, $end+1, count($a)-$end)
    " />
</xsl:function>

<xsl:function name="so:swap" as="xs:integer*">
  <xsl:param name="a" as="xs:integer*" />
  <xsl:param name="x" as="xs:integer" />
  <xsl:param name="y" as="xs:integer" />

  <xsl:sequence select="
    for $p in 1 to count($a) return $a[
        if ($p eq $x) then $y
        else if ($p eq $y) then $x
        else $p]" />
</xsl:function>

<xsl:function name="so:one-siftDown" as="xs:integer*">
  <xsl:param name="a" as="xs:integer*" />
  <xsl:param name="root" as="xs:integer" />

  <xsl:variable name="left-child" select="$root * 2" as="xs:integer" />
  <xsl:variable name="right-child" select="$left-child + 1" as="xs:integer" />
  <xsl:variable name="palette" select="($a[$root], $a[$left-child], $a[$right-child])" />
  <xsl:choose>
    <xsl:when test="exists( $palette)">
      <xsl:variable name="max-pos" select="index-of($palette,max($palette))[1]" />
      <xsl:choose>
        <xsl:when test="($left-child le count($a)) and ($max-pos eq 2)">
          <xsl:sequence select="so:one-siftDown(
            so:swap( $a, $root, $left-child),
            $left-child)" />
        </xsl:when>
        <xsl:when test="($right-child le count($a)) and ($max-pos eq 3)">
          <xsl:sequence select="so:one-siftDown(
            so:swap( $a, $root, $right-child),
            $right-child)" />
        </xsl:when>
        <xsl:otherwise>
          <xsl:sequence select="$a" />
        </xsl:otherwise>
      </xsl:choose>
    </xsl:when>
    <xsl:otherwise>
      <xsl:sequence select="$a" />
    </xsl:otherwise>
  </xsl:choose>
</xsl:function>

</xsl:stylesheet>

笔记

  1. swap() 函数是 OP 在问题中要求的交换函数，除了它专门用于整数，而不是项目。
  2. 您可以使用 Dimitre 的 swap 或 mine 实现。我很想知道 OP 对哪个更具可读性的意见。甚至还有第三种方法——您可以结合 subsequence() 和连接运算符 ( ,) 。
  3. 作为学术讨论点，这个样式表在 2012 年 7 月 10 日的 XSLT 3.0 工作草案中会非常简单，因为该算法非常适合新的fn:fold-left() 函数。如果这个问题被概括为按任何功能对任何事物进行排序，那么这个任务将是 XSLT 3.0 草案的一个很好的展示案例。恕我直言，XSLT 3.0 草案的展示任务非常稀缺。我一直在努力收集它们。
于 2012-11-19T03:33:07.617 回答