9

例如，当我在 OCaml 中有两个列表时

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

和

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

有没有一种有效的方法来获得这两个列表的交集？IE：

[3; 5; 7]

因为我不喜欢为列表 e1 中的每个元素扫描列表 e2 中的每个元素，因此创建了一个 n^2 阶的大哦。

4

7 回答 7

8

正如 Franck 和 Rémi 所说，将列表转换为集合（来自 stdlib 模块 Set）需要 n log(n)，然后 Sets 提供了交集的线性实现。Franck 还提到了对列表进行排序的等效替代方法，然后以同步的方式遍历它们。这些大致相同（顺便说一下，在这两种情况下，您都需要能够对列表中的元素提供总排序）。

如果交叉点是算法的重要组成部分，并且您希望它们在两组元素略有不同的情况下更快，则需要切换到可合并结构，例如帕特里夏树。请参阅http://www.lri.fr/~filliatr/ftp/ocaml/ds/pt*中的文件。

如果您需要在所有情况下都快速交集，则可以使用散列约束 Patricia 树。Hash-consing 有助于识别结构上相同的子树，并通过降低比较成本来帮助为先前的操作构建有效的缓存。

Patricia 树不能使用任意类型作为键（通常它们以整数作为键）。但是您有时可以通过在创建时为您打算用作键的每个值编号来解决此限制。

于 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（语法方面），但通常你可以通过两种方式做到这一点：

  1. 如果您的语言支持集合数据结构，则将两个列表都转换为集合并使用集合交集操作。

  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.) 遍历第一个列表：对于遇到的每个元素，将相应偏移量的布尔值设置为“真”；在您的示例中，这将产生

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]

于 2012-01-16T17:45:42.970 回答
1

我不认为我的解决方案是 O(n)，但它很短，对于不受复杂性约束的人来说可能很有趣（因为这个答案是“Ocaml intersect list”的第一个搜索结果之一）

当交集不为空时，此函数返回 true。换句话说，它检查两个列表是否共享元素，如果是，则为真，否则为假。

let intersect l1 l2 =
    List.fold_left (fun acc x -> if (List.exists (fun y -> y = x) l1) then true else acc) false l2;;

非常相似，此函数返回实际的交点。

let intersect l1 l2 =
    List.fold_left (fun acc x -> if (List.exists (fun y -> y = x) l1) then x::acc else acc) [] l2;;

如果我的解决方案不正确，请随时纠正我。它应该是多态的，因为 x 和 y 可以是任何可以比较的类型。

于 2019-04-05T20:05:37.577 回答
0

正如之前的发帖人所说，这是“OCaml 中的相交列表”的首批搜索结果之一，因此我在这里发布了一个简单的答案，并没有解决对复杂性的担忧。

    # let e1 = [3; 4; 5; 6; 7];;
    # let e2 = [1; 3; 5; 7; 9];;
    # List.filter (fun x -> List.mem x e1) e2;;
    - : int list = [3; 5; 7]
    #
于 2021-05-12T19:14:08.810 回答