在Erlang中测试集合的相等性

Question

在Erlang中测试集合的相等性

4

给定一个用于集合的数据结构，测试两个集合是否相等似乎是一项理想的任务，事实上许多实现都允许这样做（例如 Python 中的内置集合）。

Erlang 中有不同的集合实现：sets、ordsets、gb_sets。它们的文档没有说明是否可以使用术语比较（“==”）来测试相等性，也没有提供显式函数来测试相等性。

一些简单的情况似乎允许使用“==”进行相等性测试，但我有一个更大的应用程序，在其中我能够生成相等的 sets 和 gb_sets（使用下面的函数测试），但它们在使用“==”比较时并不相等。对于 ordsets，它们总是相等的。不幸的是，我还没有找到一种方法来为相等的集合与“==”不相等的情况提供一个最小的示例。

为了可靠地测试相等性，我使用以下基于此关于集合相等的定理的函数：

%% @doc Compare two sets for equality.
-spec sets_equal(sets:set(), sets:set()) -> boolean().
sets_equal(Set1, Set2) ->
    sets:is_subset(Set1, Set2) andalso sets:is_subset(Set2, Set1).

我的问题：

为什么Erlang集合实现没有提供明确的相等测试？
如何解释使用“==”测试不同集合实现的集合相等性之间的差异？
如何生成一个关于集合sets的最小示例，其中“==”不会比较相等，但根据上述代码，这些集合是相等的？

对第2个问题的一些想法：

sets的文档说明，“集合的表示未定义”，而ordsets的文档则表示“ordset是集合的一种表示方法”。gb_sets的文档没有给出任何可比较的指示。以下评论来自sets实现的源代码，似乎重申了文档中的说法：

请注意，由于键的顺序未定义，因此我们可以在桶内自由地重新排序键。

我的理解是，在Erlang中，“==”的术语比较作用于集合的表示形式，即仅当两个集合的表示完全相同时，它们才会进行相等比较。这可以解释不同集合实现的不同行为，但也加强了问题，为什么没有明确的相等比较。

- jvf

1

我认为没有明确的相等性测试的特定原因。如果您提交一个在所有三个集合实现中实现这样一个函数的拉取请求，它可能会被接受。 - legoscia

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- I GIVE TERRIBLE ADVICE · Accepted Answer

ordsets被实现为一个有序列表，实现方式相当开放且可见。它们将会比较相等（==），尽管==意味着1.0等于1。它们不会比较严格相等（=:=）。

sets被实现为一种哈希表形式，其内部表示形式不适合任何形式的直接比较；由于哈希冲突的发生，最后添加的元素将被添加到给定哈希条目的列表中。这个添加操作对元素添加的顺序敏感。

gb_sets被实现为一种通用平衡树，树的结构确实取决于插入元素的顺序以及重新平衡的时间。它们不能直接进行比较。

要比较两个相同类型的集合，一种简单的方法是调用Mod:is_subset(A,B) andalso Mod:is_subset(B,A)--当两个集合相等时，它们只能是彼此的子集。