F#：从 seq 中删除重复项很慢

我正在尝试编写一个函数，根据给定的相等函数确定，从seq<'a>但有一个转折：我需要last从一系列重复项中进行复制，使其进入结果序列。例如，如果我有一个序列[("a", 1); ("b", 2); ("b", 3); ("b", 4); ("c", 5)]，我正在使用fun ((x1, y1),(x2, y2)) -> x1=x2检查是否相等，我想看到的结果是[("a", 1); ("b", 4); ("c", 5)]。这个函数的要点是我有数据点进来，有时数据点合法地具有相同的时间戳，但我只关心最新的一个，所以我想扔掉前面具有相同时间戳的数据点。我实现的功能如下：

let rec dedupeTakingLast equalityFn prev s = seq {
     match ( Seq.isEmpty s ) with
     | true -> match prev with 
                 | None -> yield! s
                 | Some value -> yield value
     | false ->
         match prev with 
         | None -> yield! dedupeTakingLast equalityFn (Some (Seq.head s)) (Seq.tail s) 
         | Some prevValue -> 
             if not (equalityFn(prevValue, (Seq.head s))) then 
                 yield prevValue
             yield! dedupeTakingLast equalityFn (Some (Seq.head s)) (Seq.tail s)
}

就实际工作而言，它是有效的：

> [("a", 1); ("b", 2); ("b", 3); ("b", 4); ("c", 5)] 
  |> dedupeTakingLast (fun ((x1, y1),(x2, y2)) -> x1=x2) None 
  |> List.ofSeq;;
val it : (string * int) list = [("a", 1); ("b", 4); ("c", 5)]

然而，就性能而言，这是一场灾难：

> #time
List.init 1000 (fun _ -> 1) 
|> dedupeTakingLast (fun (x,y) -> x = y) None 
|> List.ofSeq
#time;;    
--> Timing now on    
Real: 00:00:09.958, CPU: 00:00:10.046, GC gen0: 54, gen1: 1, gen2: 1
val it : int list = [1]    
--> Timing now off

显然我在这里做了一些非常愚蠢的事情，但我看不出它是什么。性能损失从何而来？我意识到有更好的实现，但我特别想了解为什么this实施速度如此之慢。

编辑：仅供参考，设法以依赖于的功能风格实现了一个不错的实现Seq.仅功能。性能还不错，大约是命令式实现时间的 1.6 倍@gradbot下面使用迭代器。看来问题的根源在于使用Seq.head and Seq.tail在我最初的努力中的递归调用中。

let dedupeTakingLastSeq equalityFn s = 
    s 
    |> Seq.map Some
    |> fun x -> Seq.append x [None]
    |> Seq.pairwise
    |> Seq.map (fun (x,y) -> 
            match (x,y) with 
            | (Some a, Some b) -> (if (equalityFn a b) then None else Some a)  
            | (_,None) -> x
            | _ -> None )
    |> Seq.choose id

性能问题来自对 Seq.tail 的嵌套调用。这是源代码Seq.tail

[<CompiledName("Tail")>]
let tail (source: seq<'T>) =
    checkNonNull "source" source
    seq { use e = source.GetEnumerator() 
          if not (e.MoveNext()) then 
              invalidArg "source" (SR.GetString(SR.notEnoughElements))
          while e.MoveNext() do
              yield e.Current }

如果你打电话Seq.tail(Seq.tail(Seq.tail(...)))编译器无法优化由以下方法创建的枚举器GetEnumerator()。后续返回的元素必须遍历每个嵌套序列和枚举器。这导致每个返回的元素都必须冒泡通过所有先前创建的序列，并且所有这些序列也必须增加其内部状态。最终结果是运行时间为 O(n^2)，而不是线性 O(n)。

不幸的是，目前还没有办法在 F# 中以函数式风格表示这一点。您可以使用列表 (x::xs)，但不能使用序列。在语言获得更好的序列原生支持之前，不要在递归函数中使用 Seq.tail。

使用单个枚举器将解决性能问题。

let RemoveDuplicatesKeepLast equals (items:seq<_>) =
    seq {
        use e = items.GetEnumerator()

        if e.MoveNext() then
            let mutable previous = e.Current

            while e.MoveNext() do
                if not (previous |> equals e.Current) then 
                    yield previous
                previous <- e.Current

            yield previous
    }

let test = [("a", 1); ("b", 2); ("b", 3); ("b", 4); ("c", 5)]
let FirstEqual a b = fst a = fst b

RemoveDuplicatesKeepLast FirstEqual test
|> printf "%A"

// output
// seq [("a", 1); ("b", 4); ("c", 5)]

该答案的第一个版本具有上述代码的递归版本，没有突变。