5

私は 2 つのコレクションを持っています (それらはたまたま配列ですが、実際には問題ではないと思います):LとR. どちらもソートされているので、比較したいと思います。最終的に 2 つのコレクションを作成したいと考えています。1 つは入力配列ごとに 1 つは、もう一方にはなかった項目を含む配列です。

から最初のアイテムを取得してL検索Rし、一致するものがない場合は、それを「一意の」コレクションに追加することができます ( Lu)。しかし、それは非常に非効率的であり、近い将来、非常に大きなコレクションを処理する必要があると予想しています。

私はおそらく「石けり遊び」について考えました：

  • ステップ 1: 2 つのリスト と を取りL、各リストの先頭 (と)Rを比較します。l :: Lr :: R

    • 分岐 1: l<の場合r、 に追加lして再帰し、とLuを渡すLr :: R

    • 分岐 2: l>の場合r、 に追加rして再帰し、とRuを渡すl :: LR

    • 分岐 3: l=rの場合、再帰的に渡してL、R

  • Luステップ2: 戻るRu

私はこの関数を書くことができますが、努力する前に、これを行うことができる関数が既に存在するかどうか疑問に思っていました. これは珍しくないシナリオのように思えます。私は常に、既存のソリューションを使用して独自のソリューションを展開したいと考えています。

(また、このアルゴリズムにもっとわかりやすい名前があれば、それが何と呼ばれているのか知りたいです。)

4

1 に答える 1

9

（上記の質問を約2時間前に書きました。それ以来、私は自分で答えを見つけました。以下は私が見つけたものです。）

集合論では、L にあるが R にはない項目の「リスト」は、「L における R の相対的補数」として知られ、「L と R の集合論的差異」としても知られています。

(ウィキペディアの補数 (集合論)の記事を参照)

数学言語である 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 型はマイナス演算子をオーバーロードしています。Set.difference最初のパラメーターから2番目のパラメーターを減算するだけなので、実際には次のように使用できます。

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

> val Lu : int [] = [|1|]
> val Ru : int [] = [|4|]
于 2014-01-27T19:21:27.167 に答える