如何在OCaml中交叉两个列表？

Question

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

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

和

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

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

[3; 5; 7]

因为我不喜欢在列表e1中扫描列表e1中每个元素的每个元素,因此创建了一个大的订单n ^ 2.

Answer 1

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

如果交叉点是算法的一个重要部分,并且您希望它们在两组元素略有不同的情况下更快,则需要切换到可合并的结构,例如Patricia树.查看文件pt*中http://www.lri.fr/~filliatr/ftp/ocaml/ds/.

如果你需要在所有情况下快速交叉,你可以使用哈希模式Patricia树.Hash-consing有助于识别结构相同的子树,并通过比较便宜来帮助为以前的操作构建有效的缓存.

Patricia树不能使用任意类型作为键(通常它们以int作为键表示).但是,您有时可以通过在创建时将每个要用作键的值编号来解决此限制.

Answer 2

我的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)时间运行.基本上它会检查每个列表的第一个元素.如果它们相等,则将递归调用的结果存储到它们的尾部,然后检查存储结果的头部是否等于列表的头部.如果不是,则插入它,否则它是重复的并且忽略它.

如果它们不相等,那么它只会向较小的那个前进.