XPath 2.0中表示集合相等的惯用方式

Question

如果$A和$B是序列，那么测试$A和$B的集合相等性的惯用方式是什么？我知道（$A = $B）的存在语义行为使得这个表达式不是答案。而deep-equal()的排序语义也禁止我使用它。

我的冲动是使用：

((every $a in $A satisfies $a = $B) and (every $b in $B satisfies $b = $A))

通过谷歌搜索，我惊讶地发现关于集合相等性测试的信息非常少（确切地说，我什么也没找到），并且在 @Michael-Kay 的第8、9、10或13章中也没有提到它。很难相信我是第一个XPath用户遇到这个需求的。这让我想知道我是否提出了错误的问题。

- Cary Millsap

Answer 1

一个有趣且提出得很好的问题！在我看来，使用every和satisfies来克服序列比较的存在属性是一种非常有效和规范的方法。

但是，既然您问到另一种方法：如何在使用deep-equal()比较之前对序列进行排序呢？让我们假设以下样式表中有两个序列：

<?xml version="1.0" encoding="UTF-8" ?>
<xsl:transform xmlns:xsl="http://www.w3.org/1999/XSL/Transform" version="2.0">
    <xsl:output method="text"/>

    <xsl:variable name="A" select="('a','b','c')"/>
    <xsl:variable name="B" select="('a','c','b')"/>

    <xsl:template match="/">
      <xsl:choose>
          <xsl:when test="deep-equal($A,$B)">
              <xsl:text>DEEP-EQUAL!</xsl:text>
          </xsl:when>
          <xsl:otherwise>
              <xsl:text>NOT DEEP-EQUAL</xsl:text>
          </xsl:otherwise>
      </xsl:choose>
    </xsl:template>

</xsl:transform>

当然，这个转换会返回以下内容。

NOT DEEP-EQUAL

但是，如果在比较这些序列之前对它们进行排序，例如使用一个自定义函数来使用xsl:perform-sort进行排序，请参阅规范的相关部分：

<?xml version="1.0" encoding="UTF-8" ?>
<xsl:transform xmlns:xsl="http://www.w3.org/1999/XSL/Transform" version="2.0"
    xmlns:local="www.local.com" extension-element-prefixes="local"
    xmlns:xs="http://www.w3.org/2001/XMLSchema">
    <xsl:output method="text"/>

    <xsl:variable name="A" select="('a','b','c')"/>
    <xsl:variable name="B" select="('a','c','b')"/>

    <xsl:template match="/">
      <xsl:choose>
          <xsl:when test="deep-equal(local:sort($A),local:sort($B))">
              <xsl:text>DEEP-EQUAL!</xsl:text>
          </xsl:when>
          <xsl:otherwise>
              <xsl:text>NOT DEEP-EQUAL</xsl:text>
          </xsl:otherwise>
      </xsl:choose>
    </xsl:template>

    <xsl:function name="local:sort" as="xs:anyAtomicType*">
        <xsl:param name="in" as="xs:anyAtomicType*"/>
        <xsl:perform-sort select="$in">
            <xsl:sort select="."/>
        </xsl:perform-sort>
    </xsl:function>

</xsl:transform>

然后，结果将是：

DEEP-EQUAL!

编辑: 实际上，集合相等意味着不仅顺序无关紧要，而且重复项也不会有影响。 因此，正确的集合相等意味着还需对序列变量应用distinct-values()：

<xsl:when test="deep-equal(local:sort(distinct-values($A)),local:sort(distinct-values($B)))">

- Mathias Müller

Answer 2

首先，这取决于您如何评估项目之间的相等性，例如您是否使用“=”，“is”，“eq”或“deep-equal”来比较两个项目？您自己的答案表明您考虑使用“=”，它在应用于项目时与“eq”几乎相同，只是具有稍微不同的转换规则。恰好，它不是与集合一起使用的好运算符，因为它不是可传递的：untypedAtomic（“4”）= 4，untypedAtomic（“4”）=“4”，但不是（4 =“4”）。所以让我们假设“eq”，它是传递的，除了涉及“几乎相等”的数值舍入的极端情况。

然后我倾向于建议（正如其他人所做的那样）

deep-equal(sort($A), sort($B)) 

除了某些数据类型（例如QNames）具有定义相等运算符但未定义排序的情况外，它适用于整数和字符串，但不适用于QNames。

显然，在您的“冲动”解决方案中提供了O(n^2)方法，但是否有更好的方法呢？

怎么样呢？

let $A := count(distinct-values($a))
let $B := count(distinct-values($b))
let $AB := count(distinct-values(($a, $b))
return $A = $AB and $B = $AB

这应该是O(n log n)的。

- Michael Kay