1

我是带有 Xpath2 的 XSLT3 的 Saxon 9.5EE 实现，并正在寻找最快的方法来识别排序序列 $seq 中小于某个给定值 $value 的最大元素。

据我所知，没有什么相当于序列的“preceding::sibling”。这意味着 Xpath 在遍历序列时不如遍历 XML 树时灵活。

也就是说，你不能说$seq[。gt $value][1]/preceding-sibling:item[1] 因为“/”只为节点定义，“preceding-sibling”不会引用序列，而是引用相关节点的 XML 树。

反正...

我找到了两种方法来做到这一点，但它们似乎不必要地复杂。

一种方法是：

$seq[($seq!(if(. gt $value) then position() else ()))[1] - 1]

另一种方法是

<xsl:iterate select="$seq">
    <xsl:variable name="pos" select="position()"/>
<xsl:if test=". gt $trial">
    <xsl:text>
</xsl:text>
    <xsl:sequence select="$seq[$pos - 1]"/>
    <xsl:break/>
</xsl:if>
</xsl:iterate>

有没有更好的办法？

顺便说一句，测试这两个选项得到了有趣的结果。如果我只是在寻找相关项目的位置，那么它们最终在性能上几乎相同。

但是，如果我真的对值本身感兴趣，则该选项会压碎另一个……大概是因为由于迭代命令，该序列已经在内存中准备好了。

4

3 回答 3

1

怎么样：

$seq[. lt $value][last()]
于 2013-09-17T18:19:56.157 回答
0

如果您的实现将序列存储为数组，最快的方法是使用二进制搜索O(log n)，而不是O(n)像其他答案的线性搜索一样。

如果您的实现可以通过保持范围引用来计算 O(1) 中的子序列，您可以使用：

 function f ($seq, $value, $best) { 
    if (count($seq) = 0) then $best
    else let $midi := (count($seq) + 1) idiv 2
    return if ($seq[$midi] <= $value) then f(subsequence($seq, $midi + 1), $value, $seq[$midi])  
    else f(subsequence($seq, 1, $midi - 1), $value, $best)
  }

否则，您可以将子序列保留为函数参数：

 function f ($seq, $first, $last, $value, $best) { 
    if ($last < $first) then $best
    else let $midi := $first + ($last - $first) idiv 2
    return if ($seq[$midi] <= $value) then f($seq, $midi + 1, $last, $value, $seq[$midi])  
    else f($seq, $first, $midi - 1, $value, $best)
  }
  function call-f($seq, $value) {
    f($seq, 1, count($seq), $value, ())
  }
于 2013-10-22T20:12:13.517 回答
0

我认为递归函数是最优雅的解决方案：

function f ($seq, $value, $bestSoFar) {
   if (head($seq) > $value)
   then $bestSoFar
   else f(tail($seq), $value, head($seq))
}
于 2013-09-17T20:42:18.250 回答