9

たとえば、OCamlに2つのリストがある場合

e1 = [3; 4; 5; 6; 7]

と

e2 = [1; 3; 5; 7; 9]

これら 2 つのリストの交点を取得する効率的な方法はありますか? すなわち:

[3; 5; 7]

リストe1のすべての要素に対してリストe2のすべての要素をスキャンするのは好きではないため、次数n ^ 2の大きなOhを作成します。

4

7 に答える 7

8

FranckとRémiが言ったように、リストを（stdlibモジュールSetから）セットに変換するにはn log（n）かかり、Setsは交差の線形実装を提供します。フランクはまた、リストをソートし、同期された方法でそれらをトラバースするための同等の代替手段についても言及しました。これらはほぼ同じです（ちなみに、どちらの場合も、リスト内の要素の全順序を指定できる必要があります）。

交差がアルゴリズムの重要な部分であり、わずかに異なる2セットの要素の場合に交差を高速化したい場合は、パトリシアツリーなどのマージ可能な構造に切り替える必要があります。http://www.lri.fr/~filliatr/ftp/ocaml/ds/のファイルpt*を参照してください。

すべての場合に交差を高速にする必要がある場合は、ハッシュを考慮したパトリシアツリーを使用する可能性があります。ハッシュコンシングは、構造的に同一のサブツリーを認識するのに役立ち、比較を安価にすることで、以前の操作のための効率的なキャッシュを構築するのに役立ちます。

パトリシアツリーは、キーとして任意のタイプを使用することはできません（通常、キーとしてintで表示されます）。ただし、作成時にキーとして使用する予定の各値に番号を付けることで、この制限を回避できる場合があります。

于 2010-03-04T13:44:29.000 に答える
5

私のOCamlは最高ではありませんが、ソートされたリストと交差するこの関数を一緒にハックしました:

let rec intersect l1 l2 =
    match l1 with [] -> []
        | h1::t1 -> (
          match l2 with [] -> []
              | h2::t2 when h1 < h2 -> intersect t1 l2
              | h2::t2 when h1 > h2 -> intersect l1 t2
              | h2::t2 -> (
                match intersect t1 t2 with [] -> [h1]
                    | h3::t3 as l when h3 = h1 -> l
                    | h3::t3 as l -> h1::l
              )
        );;

これは O(n+m) 時間で実行されます。基本的に、各リストの最初の要素をチェックします。それらが等しい場合、再帰呼び出しの結果を末尾に格納し、格納された結果の先頭がリストの先頭と等しいかどうかを確認します。そうでない場合は挿入し、そうでない場合は重複しているため無視します。

等しくない場合は、どちらか小さい方が進みます。

于 2010-03-04T16:41:21.740 に答える
4

私は OCaml について (構文的に) 知りませんが、一般的に次の 2 つの方法でこれを行うことができます。

  1. 言語が Set-datastructure をサポートしている場合は、両方のリストを Set に変換し、set-intersection 操作を使用します。

  2. より一般的には、両方のリストを並べ替えてから、並べ替えられたリストをスキャンします。これにより、重複をより効率的に見つけることができます。並べ替えに n log(n) を使用すると、線形時間で重複を見つけることができます。

于 2010-03-04T11:49:35.047 に答える
3

@Frankが示唆したように、これまでのベストアンサーではありませんが、セットを使用してこの問題を解決できますが、OCamlでこれを実現する方法を示す短いコードリストを次に示します。

module Int_set = Set.Make (struct
                             type t = int
                             let compare = compare
                           end);;

(* iters through a list to construct a set*)
let set_of_list = List.fold_left (fun acc x -> Int_set.add x acc) Int_set.empty;;

let e1 = [3; 4; 5; 6; 7];;
let e2 = [1; 3; 5; 7; 9];;

let s1 = set_of_list e1;;
let s2 = set_of_list e2;;

(*result*)
let s3 = Int_set.inter s1 s2;;


(*testing output*)
Int_set.iter (fun elt -> print_int elt;print_string "\n") s3;;

出力は次のとおりです。

3
5
7
- : unit = ()
于 2010-03-04T20:01:58.147 に答える
1

リストに限られたサイズの整数しか含まれていない場合は、O(n) にも解決策があります。

1.) 元のリストで最大の整数値に 1 を加えたサイズのブール値の配列を作成します (例: '9+1')。すべてのフィールドを false に設定します。

let m = Array.create 10 false

->[|false; false; false; false; false; false; false; false; false; false|]

2.) 最初のリストを反復処理します。遭遇するすべての要素について、それぞれのオフセットを持つブール値を「true」に設定します。あなたの例では、これは

List.iter (fun x -> m.(x) <- true) e1

->[|false; false; false; true; true; true; true; true; false; false|]

3.) 2 番目のリストをフィルター処理し、配列内の対応するフィールドが true である要素のみを保持します。

List.filter (fun x -> m.(x) = true) e2

->[3; 5; 7]

于 2012-01-16T17:45:42.970 に答える