在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用户。这让我想知道我是否提出了错误的问题。

Answer 1

首先，它取决于您如何评估项目之间的平等，例如，您是使用“=”，“是”，“eq”还是“深度相等”来比较两个项目？你自己的答案表明你正在考虑“=”，这与应用于项目时的“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）。

Answer 2

一个有趣且问题很好的问题！在我看来，使用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的自定义函数，请参阅relevant part of the specification：

<?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)))">