如何在OCaml中交叉兩個列表？

Question

當我在OCaml的兩個列表，例如

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

和

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

是否有一個有效的辦法讓這兩個列表的交集？ 即：

[3; 5; 7] 

因爲我不喜歡掃描列表E2的每一個元素在列表E1的每一個元素，從而創造秩序大哦N^2。

Answer 1

由於裏貝里和雷米說，轉換您的列表，以套（從STDLIB模塊集）費用的n log（n）的，然後設置提供了路口的線性執行。弗蘭克還提到了對列表進行排序的等價替代方法，然後以同步的方式遍歷它們。這些大致相同（順便說一句，在這兩種情況下，您都需要能夠對列表中的元素進行總體排序）。

如果交叉點是算法的重要組成部分，並且希望在兩組元素稍微不同的情況下它們更快，則需要切換到可合併的結構（如Patricia樹）。請參閱http://www.lri.fr/~filliatr/ftp/ocaml/ds/中的文件pt*。

如果您需要路口要快在所有情況下，你必須使用哈希consed帕特里夏樹的可能性。 Hash-Consing有助於識別結構相同的子樹，並通過比較便宜的方式幫助爲以前的操作構建高效的緩存。

帕特里夏樹不能使用任意類型作爲鍵（通常它們以鍵作爲鍵呈現）。但是有時您可以通過創建每個您打算用作關鍵值的數字來解決此限制。

Answer 2

我不知道OCaml的（語法明智），但一般可以通過兩種方式來實現：

1. 如果你的語言有一個Set-數據結構支持，那麼這兩個列表轉換成集並使用set-intersection操作。

2. 更一般地說：對兩個列表進行排序，然後掃描排序後的列表，這樣可以使重複查找效率更高。您需要n log（n）進行排序，然後可以在線性時間內找到重複項。

Answer 3

我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）時間運行。基本上它會檢查每個列表的第一個元素。如果它們相等，則將遞歸調用的結果存儲到它們的尾部，然後檢查存儲結果的頭部是否與列表的頭部相等。如果不是，它會插入它，否則它是重複的，它會忽略它。

如果它們不相等，它只是進入哪一個更小。

Answer 4

由於@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 =() 

Answer 5

如果您的列表僅包含有限大小的整數，也有在O溶液（N）：

1.）創建y的大小的布爾值的陣列您的原始列表中最大的整數值加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.）在所述第二列表中篩選，僅保留那些元件，其中在陣列中的對應字段爲真

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

- >[3; 5; 7]