比较两个列表中每个

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

• 第2步：返回Lu a第二Ru

我可以写这个功能，但我付出努力之前，我在想，如果一个函数已经存在，可以帮我这个忙。这似乎是一个不常见的情况，我总是宁愿使用现有的解决方案来滚动我自己的。

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

Answer 1

（我写上面约2小时前的问题。从那时起，我发现回答我自己的，下面是我发现的。）

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

（参见Wiki pedia的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|]