Ich versuche, eine Funktion zu schreiben, die aufeinanderfolgende Duplikate, wie durch eine gegebene Gleichheitsfunktion bestimmt, aus einem @ entfernseq<'a> aber mit einer Wendung: Ich brauche diezuletz duplicate aus einer Reihe von Duplikaten, um die resultierende Sequenz zu erstellen. Zum Beispiel, wenn ich eine Sequenz habe[("a", 1); ("b", 2); ("b", 3); ("b", 4); ("c", 5)], und ich benutzefun ((x1, y1),(x2, y2)) -> x1=x2 um auf Gleichheit zu prüfen, ist das Ergebnis, das ich sehen möchte,[("a", 1); ("b", 4); ("c", 5)]. Der Punkt dieser Funktion ist, dass Datenpunkte hereinkommen, bei denen manchmal Datenpunkte legitimerweise den gleichen Zeitstempel haben, mir aber nur der neueste wichtig ist, sodass ich die vorhergehenden mit dem gleichen Zeitstempel wegwerfen möchte. Die von mir implementierte Funktion lautet wie folgt:

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)
}

In Bezug auf die tatsächliche Ausführung der Arbeit funktioniert es:

> [("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)]

n Bezug auf die Leistung ist es jedoch eine Katastrophe:

> #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

Clearly Ich mache hier etwas sehr dummes, aber ich kann nicht sehen, was es ist. Woher kommt der Performance-Hit? Mir ist klar, dass es bessere Implementierungen gibt, aber ich bin speziell daran interessiert zu verstehen, warumDie Implementierung ist so langsam.

EDIT: Zu Ihrer Information, es ist uns gelungen, eine anständige Implementierung im funktionalen Stil zu erzielen, der auf @ basierSeq. funktioniert nur. Die Leistung ist in Ordnung. Die Zeit für die Implementierung im imperativen Stil durch @ beträgt etwa das 1,6-fach@ gradbot darunter verwendet Iteratoren. Es scheint, dass die Wurzel des Problems die Verwendung von @ iSeq.head undSeq.tail in rekursiven Aufrufen in meiner ursprünglichen Anstrengung.

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