Erlang

Question

我目前正在尝试了解 Erlang 集合的行为，当我在字符串 Anagrams 上计算集合时。在我的理解中，两个字谜应该产生两组相同的字符串。

Set1 = sets:from_list("orchestra"). 
Set2 = sets:from_list("carthorse"). 
Set1 =:= Set2. %% true

但是，使用 sets:intersection 我们得到了一个不同的集合，它不等于前两个集合。

Intersection = sets:intersection(Set1, Set2). 
Intersection =:= Set1. %% false
Intersection =:= Set2. %% false

根据 Erlang 中集合交集的计算方式，这种行为是否有特殊原因？非常感谢！

Answer 1

=:=运算符比较Set1和Intersection的表示，但不能保证表示是什么，也不能保证同一组只有一种表示。

sets 的文档仅在描述如何比较集合的元素而不是集合本身时谈论 =:=。

对于集合相等，可以定义

set_eq(S1, S2) ->
    sets:is_subset(S1, S2) andalso sets:is_subset(S2, S1).

Answer 2

sets 模块的实现不保证两个集合可以与 =:= 进行比较，即使它们包含相同的元素。内部数据结构可以不同。您可以使用 is_subset/2 或 subtract/2 之类的操作（相对低效），或者您可以使用 to_list/1 然后 lists:sort/1 来获得可以直接比较的两个列表。但是，如果您无论如何都是从字符串（字符列表）开始的，那么最好立即使用 ordsets。这些是有序列表，您可以将其作为集合进行操作，并且可以直接进行比较。对于小型集合，它们通常比 sets 更有效。

> Set1 = ordsets:from_list("orchestra").
"acehorst"
> Set2 = ordsets:from_list("carthorse").
"acehorst"
> Set1 =:= Set2.
true
> Intersection = ordsets:intersection(Set1, Set2).
"acehorst"
> Intersection =:= Set1.
true
> Intersection =:= Set2.
true

Answer 3

让我们看一下代码，看看沿途发生了什么。

我们正在定义 2 个集合

Set1 = sets:from_list("orchestra"). 
{set,8,16,16,8,80,48,
     {[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[]},
     {{[],"sc",[],[],[],"o","r","e","h",[],[],"a","t",[],[],[]}}}

和

Set2 = sets:from_list("carthorse"). 
{set,8,16,16,8,80,48,
     {[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[]},
     {{[],"sc",[],[],[],"o","r","e","h",[],[],"a","t",[],[],[]}}}

其中第二行表示使用表示创建的值。所以根据上面的定义，我们推断选择用于存储集合的表示是一个元组。

我们可以参考 Erlang 参考手册的 Term Comparison 部分，其中指出

...Lists are compared element by element. Tuples are ordered by size, two tuples with the same size are compared element by element...

将其作为不变量，现在让我们看一下 intersection

之后的集合

Intersection = sets:intersection(Set1, Set2).
{set,8,16,16,8,80,48,
     {[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[]},
     {{[],"cs",[],[],[],"o","r","e","h",[],[],"a","t",[],[],[]}}}

同样，这是一个集合，它具有与元组相同的底层表示，但是如果我们查看最后一个元素，则会有一个字符串（本质上是 Erlang 中的字符列表）"cs"，它是我们定义Set1和Set2时在同一个地方的值不同。因此，根据 Term Comparison.

的不平等

现在，让我们尝试将Intersection中的子值"cs"更改为"sc"，然后根据Term Comparison规则，两个集合必须满足相等。

Improvised_Intersection = setelement(9, Intersection, {setelement(2, element(1, element(9, Intersection)), "sc")}).
{set,8,16,16,8,80,48,
     {[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[]},
     {{[],"sc",[],[],[],"o","r","e","h",[],[],"a","t",[],[],[]}}}

现在让我们将 Improvised_Intersection 与 Set1 和 Set2 进行比较，得到

Improvised_Intersection =:= Set1.                                                                                  
true

Improvised_Intersection =:= Set2.                                                                                  
true

Intersection =:= Improvised_Intersection.
false

这只是对@Richard 和其他人已经指出的内容提供一些见解的尝试。

Erlang - 字符串到集合

Erlang - String into Set