F#删除列表中的常见元素 [英] F# deleting common elements in lists

问题描述

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

I'm trying to make a list with only one copy of each element of the original list.

例如[1; 2; 3; 3; 2]将是[1; 2; 3]或["hi";"the";"world";"hi"]将是["hi"; "the";"world"]

For example [1;2;3;3;2] would be [1;2;3] or ["hi";"the";"world";"hi"] would be ["hi";"the";"world"]

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

I'm using recursion and pattern matching, and not using the list modules.

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

Here is my attempt and thinking: I want to go through the list and look at the head, and if that element exists in the tail of the list, then I want to take that element and then remove that element from the existing list

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

推荐答案

第一个答案很简单，但是它使用具有O(log n)插入复杂度的AVL树和许多内部指针分配以及每项的高内存消耗:

The first answer is very simple, but it uses AVL tree with O(log n) insert complexity and a lot of internal pointers allocations and high memory consumption per item:

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树进行了排序，因此该不保留原始顺序，并返回排序后的元素，例如

And AVL tree is sorted, so this does not preserve the original order and returns sorted elements, e.g.

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)插入/查找且每个项目的内存较少的命令性集合.这是保留重复值的专用记录的理想数据结构.使用它，可以将通用功能编写为:

SCG.HashSet is an imperative collection with O(1) insert/lookup and less memory per item. It is the perfect data structure to keep a private track record of repeated values. Using it, one could write the common function as:

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一起使用非常简单，快速且保持顺序.这是一个很好的例子，当使用私有可变状态的能力是F#的祝福，并且与纯功能解决方案相比要快得多，而外部功能保持纯功能"且没有副作用时.

So using the List.fold with HashSet is very simple, fast and order-preserving. This is a good example when the ability to use private mutable state is F# blessing and is much faster compared to pure functional solutions, while the outer function remains "pure functional" with no side effects.

出于完整性考虑，我们可以使用AVL集实现相同的折叠逻辑.它的执行速度与第一个答案相同，是纯粹的功能"，并且保持原始顺序:

For completeness, we could implement the same fold logic using AVL set. It performs at the same speed as the first answer, is "pure functional" and keeps the original order:

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

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

P.S. Using let common (l:'T list) = HashSet(l) |> List.ofSeq does not guarantee the order of elements and is c.2x slower than the fold solution.

P.P.S.第二次升空的时间是:

P.P.S. The timing for the second asnwer is:

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

这篇关于F#删除列表中的常见元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！