1

XSLT 中以下 XPath 表达式的索引访问的时间复杂度是多少？

<xsl:value-of select="User[2]/username"/>
  1. O(log(n))
  2. O(1) 或
  3. 在）

我有一个包含数千个用户的排序xml 文件，如下所示：

<Users>
  <User>
    <idPerson>460</idPerson>
    <username>a_aker01</username>
  </User>
  <User>
    <idPerson>677</idPerson>
    <username>a_aker02</username>
  </User>
  <User>
    <idPerson>1844</idPerson>
    <username>a_aker03</username>
  </User>
  <User>
    <idPerson>2373</idPerson>
    <username>a_aker04</username>
  </User>
</Users>

我正在考虑在 XSLT 2.0 中编写一个二进制搜索函数（需要快速索引访问）以实现更快的搜索，因为

<xsl:variable name="targetId" select="2373" />
<xsl:value-of select="User[idPerson=$targetId]/username"/>

对我的需要来说太慢了。它是否执行线性搜索？

4

3 回答 3

3

的时间复杂度/Users/User[2]是特定于实现的。很可能它是一个 O(n) 线性搜索，但也许有一个足够聪明的实现可以在理想条件下在 O(1) 中完成。

但是，你为什么不直接使用xsl:key而不是创建一个二分搜索函数呢？（这也适用于 XSLT 1.0。）

<xsl:stylesheet xmlns:xsl="http://www.w3.org/1999/XSL/Transform" version="2.0">
  <xsl:output method="text"/>

  <xsl:key name="user-for-idPerson" match="/Users/User" use="number(idPerson)"/>

  <xsl:template match="/">
    <xsl:variable name="targetId" select="2373" />
    <xsl:value-of select="key('user-for-idPerson', $targetId)/username"/>
  </xsl:template>

</xsl:stylesheet>
于 2012-12-17T06:14:18.397 回答
1

这一切都取决于实施。

Saxon-HE 将使用线性搜索实现 User[idPerson=$targetId]，Saxon-EE 很可能会建立索引。

两种产品对于子轴的数值过滤都具有 O(n) 的时间复杂度，如 User[2] 中一样，但如果您使用变量 ($User[2])，则访问将花费恒定时间。

于 2012-12-17T10:42:09.063 回答
1

为了不依赖于特定 XSLT 处理器的实现，我建议应该使用一个键：

<xsl:key name="kUserById" match="User" use="idPerson"/>

然后，当您需要访问UserbyidPerson时，请执行以下操作：

key('kUserById', $targetId)

大多数 XSLT 处理器有效地实现键索引（即使用哈希表），因此，如果idPerson每个 都是唯一的，则使用上面所示User的函数进行访问的时间是 O(1) - 常数。key()

关于您的其他问题：

XSLT 中以下 XPath 表达式的索引访问的时间复杂度是多少？

<xsl:value-of select="User[2]/username"/>

对于提供的 XML 文档，它很可能是 O(1)，但是对于一个Users不仅有User孩子，而且还有其他名字的孩子的文档，访问时间可能是 O(N)——假设有 1000 个孩子被命名Customer最后两个孩子的名字是User.

我正在考虑在 XSLT 2.0 中编写一个二进制搜索函数（需要快速索引访问）以实现更快的搜索

二分搜索算法假定要搜索的对象在一个数组中（并且在数组中按索引的访问时间是 O(1)）。对于仍然没有数组数据结构的 XSLT/XPath，这种假设是错误的。

一些 XSLT 处理器（如 Saxon）可能以一种有效的方式（使用向量）实现序列，访问时间为 O(1)，但其中许多不这样做。

因此，要访问：

 $seq[$mid]

一般取O(N)，应用于这样一个序列的二分查找算法是O(N^2)。

于 2012-12-17T17:36:16.670 回答