f# - 比较每个列表中唯一项目的两个列表

Question

我有两个集合(它们碰巧是数组，但我认为这并不重要):L和 R .它们都已排序，现在我想比较它们。我想最终得到两个集合:一个用于每个输入数组，其中包含另一个不在另一个集合中的项目。

我可以从 L 取第一项然后搜索 R并且，如果没有匹配项，请将其添加到我的“唯一”集合( Lu )中。但这效率极低，我希望在不久的将来处理一些非常大的集合。

我想可能“玩跳房子”:

第 1 步:取两个列表，L和 R ，并比较每个列表的头部( l :: L 和 r :: R ):

分支 1:如果 l < r ，然后添加 l至 Lu并递归，传入 L和 r :: R

分支 2:如果 l > r ，然后添加 r至 Ru并递归，传入 l :: L和 R

分支3:如果l = r ，然后递归，传入 L和 R

第二步:返回Lu和 Ru

我可以编写这个函数，但在我开始努力之前，我想知道是否已经存在一个可以为我做到这一点的函数。这似乎是一个并不少见的场景，我总是宁愿使用现有的解决方案来推出我自己的解决方案。

(另外，如果这个算法有一个更容易识别的名字，我想知道它叫什么。)

Answer 1

(我在大约2小时前写了上面的问题。此后，我自己找到了答案。以下是我发现的。)

在集合论中，L 中而不是 R 中的项目的“列表”被称为“L 中 R 的相对补集”，也称为“L 和 R 的集合论差异”

(参见维基百科的 Complement (set theory) 文章)



F#，作为一种数学语言，将这个概念融入到它的核心库中。首先，您需要将集合构建为集合:

// example arrays:
let arr1 = [| 1; 2; 3 |]
let arr2 = [| 2; 3; 4 |]

// build the L and R sets
let L = set arr1
let R = set arr2

现在您可以调用“差异”函数并快速获取每个数组的相对补码:

let Lu = Set.difference L R |> Set.toArray
let Ru = Set.difference R L |> Set.toArray

> val Lu : int [] = [|1|]
> val Ru : int [] = [|4|]

还有一个更短的语法。 Set 类型有 overloaded the minus operator . Set.difference 只需从第一个参数中减去第二个参数，因此您实际上可以使用以下内容:

let Lu = L - R |> Set.toArray
let Ru = R - L |> Set.toArray

> val Lu : int [] = [|1|]
> val Ru : int [] = [|4|]