recursion - F# 删除列表中的公共(public)元素

Question

我正在尝试创建一个列表，其中仅包含原始列表中每个元素的一个副本。

例如，[1;2;3;3;2] 将是 [1;2;3] 或 ["hi";"the";"world";"hi"] 将是 ["hi"; “这个”;“世界”]

我使用递归和模式匹配，而不是使用列表模块。

这是我的尝试和想法:我想遍历列表并查看头部，如果该元素存在于列表的尾部，那么我想获取该元素，然后从现有元素中删除该元素列表

let rec common l =
  match l with
  | head :: tail -> if head = tail then head :: [] else head :: isolate(tail)
  | [] -> []

Answer 1

第一个答案非常简单，但它使用 AVL 树，插入复杂度为 O(log n)，并且需要大量内部指针分配，并且每个项目的内存消耗很高:

let common l = l |> Set.ofList |> Set.toList

计时结果如下:

#time "on"
let mutable temp = Unchecked.defaultof<_>
for i = 0 to 1000000 do
  temp <- common [1;2;3;3;2;4;1;5;6;2;7;5;8;9;3;2;10]
  ()
Real: 00:00:03.328, CPU: 00:00:03.276, GC gen0: 826, gen1: 0, gen2: 0

并且 AVL 树是排序的，因此不保留原始顺序并返回排序的元素，例如

common [1;2;3;3;2;4;1;5;6;2;7;5;10;8;9;3;2]
val it : int list = [1; 2; 3; 4; 5; 6; 7; 8; 9; 10]

SCG.HashSet 是一个命令式集合，具有 O(1) 插入/查找和每个项目更少的内存。它是保存重复值的私有(private)跟踪记录的完美数据结构。使用它，我们可以将通用函数编写为:

open System.Collections.Generic
let common (l:'T list) =
  let set = HashSet()
  let rec commonAux (input:'T list) (acc:'T list) : 'T list =
    match input with
    | head :: tail -> 
      if set.Add(head) then
        commonAux tail (head :: acc)
      else commonAux tail acc
    | [] -> acc
  commonAux l []
  |> List.rev

或者更简单:

let common (l:'T list) =
  let set = HashSet()
  List.fold (fun st t ->
    if set.Add(t) then t :: st
    else st
    ) [] l
  |> List.rev

两者的时间是相同的:

Real: 00:00:01.105, CPU: 00:00:01.092, GC gen0: 722, gen1: 1, gen2: 0
Real: 00:00:01.168, CPU: 00:00:01.170, GC gen0: 730, gen1: 0, gen2: 0

因此，将 List.fold 与 HashSet 一起使用非常简单、快速且保持顺序。这是一个很好的例子，使用私有(private)可变状态的能力是 F# 的加持，并且比纯函数式解决方案要快得多，而外部函数仍然是“纯函数式”，没有副作用。

为了完整性，我们可以使用 AVL 集实现相同的折叠逻辑。它的执行速度与第一个答案相同，是“纯函数”并保持原始顺序:

let common (l:'T list) =
  let rec commonAux (input:'T list) (s) (acc:'T list) : 'T list =
    match input with
    | head :: tail -> 
      if Set.contains head s then commonAux tail s acc
      else 
        commonAux tail (Set.add head s) (head :: acc)
    | [] -> acc
  commonAux l Set.empty []
  |> List.rev
Real: 00:00:02.825, CPU: 00:00:02.808, GC gen0: 908, gen1: 1, gen2: 0

附注使用 let common (l:'T list) = HashSet(l) |> List.ofSeq 不能保证元素的顺序，并且比折叠解决方案慢 c.2 倍。

P.P.S。第二个回答的时间是:

Real: 00:00:07.504, CPU: 00:00:07.394, GC gen0: 1521, gen1: 1, gen2: 0