OCaml：计算对列表中的不同值

Question

我有一个配对列表

let myList=[(0,1);(0,2);(0,3);(1,5);(2,4);(3,5);(5,4);(5,6);(4,3)];;

为了计算列表中存在的每个单独的不同值，我有这个程序

let rec flat lst  visited =
match lst with
[]->visited
| (x,y)::xs -> flat xs (x::y::visited)) ;;


let newLst = flat myList [];;

val newLst : int list =
  [4; 3; 5; 6; 5; 4; 3; 5; 2; 4; 1; 5; 0; 3; 0; 2; 0; 1]

let rec count lista = 
match lista with  
[]->0
| x::xs -> 
if (List.mem x xs) then count xs
else 1+count xs;;

count newLst;;
- : int = 7

代码运行正确，但我的问题是：

是否有更优雅或更有效的方法来做到这一点？ 例如一个独特的功能而不是两个

Answer 1

优雅没有特定的含义，所以很难回答。

我认为这是解决问题的相当不错的方法。如果你想象你有很多不同的结构（成对的列表、树等），那么转换为平面整数列表然后以不同方式处理列表的想法感觉很好。

您的解决方案的一个问题是，在最坏的情况下它是二次方的，因为您正在搜索长度为 0、1、2、... n * 2 的列表以查找 n 对。

我怀疑这不应该是生产代码，因此计算复杂度可能无关紧要。

如果您打算在列表很长且效率很重要的生产代码中执行此操作，您将直接在成对列表上进行计数。而且您不会继续在列表中搜索重复项。您会使用某种集合（甚至可能有点 vector-like 集合）来跟踪您所看到的内容。这很可能对您的预期用途来说有点矫枉过正（对我来说它看起来像是一个 class 作业）。

Answer 2

我也不会争论优雅... 另一种编写代码的方式：使用折叠操作。你的平面函数可以这样写：

let flat  = List.fold_left (fun acc (x,y) -> x::y::acc) [] ;;

Answer 3

你的解决方案基本上就是你如何在不大量求助于库函数的情况下实现的（并且以二次 worst-case 性能为代价）。您可以使用 List 库中的函数来获得更简单的解决方案，但虽然这有点简单，但它主要会教您如何使用该库，而不是将 OCaml 作为一种语言 [1]。也就是说，这里有一个解决方案可以做到这一点：

let myList=[(0,1);(0,2);(0,3);(1,5);(2,4);(3,5);(5,4);(5,6);(4,3)]

let count l =
  let open List in
  let (a, b) = split l in length (sort_uniq compare (a @ b))

let () =
  Printf.printf "=> %d\n" (count myList)

这使用 List.split 和列表附加运算符 @ 将整数对列表转换为整数列表，然后对其进行排序并删除重复项 (List.sort_uniq)，然后使用 List.length 来计算结果。由于 sort_uniq.

，运行时间为 O(n*log(n))

替代解决方案是使用 Set 或 Hashtbl 模块以比 List.mem 更有效的方式跟踪重复项，从而避免二次 worst-case 时间（但也使代码在过程中变得更加复杂）。

[1] 我在这里假设您正在学习 OCaml，因此工业强度的解决方案不一定是帮助您学习过程的最佳解决方案，具体取决于您所在的位置。

Answer 4

您的方法有效，简单易懂。它唯一的缺点是您的代码使用 Shlemiel the painter's algorithm。这意味着，处理时间表现为列表大小的二次函数。

如果要删除它，使用sets是合适的：将列表中的所有数字添加到一个集合中并计算其大小。现在时间性能在 n log(n) 中并且扩展得更好。

let myList=[(0,1);(0,2);(0,3);(1,5);(2,4);(3,5);(5,4);(5,6);(4,3)]

module IntegerSet = Set.Make(struct
    type t = int
    let compare = Pervasives.compare
  end)

let count lst0 =
  let rec loop acc lst =
    match lst with
    | [] -> IntegerSet.cardinal acc
    | (a,b)::tl -> loop IntegerSet.(add b (add a acc)) tl
  in
  loop IntegerSet.empty lst0

这段代码使用了一个累加器acc，它是通过迭代来填充的在名单之上。读取完所有列表后，返回累加器中的元素数。

OCaml：计算对列表中的不同值

OCaml: Count different value in list of pairs

ocaml