比較兩個列表中每個

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|]