gpt4 book ai didi

performance - F#:从seq中删除重复项很慢

转载 作者:行者123 更新时间:2023-12-03 22:46:17 25 4
gpt4 key购买 nike

我正在尝试编写一个函数,该函数从seq<'a>中剔除由给定的相等函数确定的连续重复项,但有一点曲折:我需要重复运行中的最后一个重复项,以使其成为结果序列。例如,如果我有一个序列[("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

显然,我在这里做的事情很愚蠢,但是我看不到它是什么。性能影响从何而来?我意识到有更好的实现,但是我特别想了解为什么这种实现如此缓慢。

编辑:仅供引用,设法以仅依赖 Seq.函数的功能风格获得了不错的实现。性能还可以,使用下面的使用迭代器的 @gradbot 所花费的命令式实现时间大约是其1.6倍。问题的根源似乎是在我最初的尝试中在递归调用中使用 Seq.headSeq.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),但不能使用序列。在该语言获得更好的序列 native 支持之前,请不要在递归函数中使用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)]

此答案的第一个版本具有上述代码的递归版本,没有任何突变。

关于performance - F#:从seq中删除重复项很慢,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/36459890/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com