Warum ist die Verwendung einer Sequenz so viel langsamer als die Verwendung einer Liste in diesem Beispiel?

Question

Hintergrund: Ich habe eine Sequenz von zusammenhängenden Daten mit Zeitstempel. Die Datenfolge weist Lücken auf, einige sind groß, andere haben nur einen einzigen fehlenden Wert.
Wenn es sich bei der Lücke nur um einen einzelnen fehlenden Wert handelt, möchte ich die Löcher mit einem Dummy-Wert füllen (größere Löcher werden ignoriert).

Ich möchte die gepatchte Sequenz nach und nach generieren und verwende daher Seq.unfold.

Ich habe zwei Versionen der Methode erstellt, um die Lücken in den Daten zu schließen.

Die erste verbraucht die Reihenfolge von Daten mit Löchern und produziert die gepatchten Reihenfolge . Dies ist, was ich will, aber die Methoden läuft schrecklich langsam, wenn die Anzahl der Elemente in der Eingabesequenz über 1000 steigt, und es wird zunehmend schlechter, je mehr Elemente die Eingabesequenz enthält.

Die zweite Methode verbraucht eine Liste der Daten mit Löchern und erzeugt die gepatchten Reihenfolge und es läuft schnell. Dies ist jedoch nicht das, was ich will, da dies die Instanziierung der gesamten Eingabeliste im Speicher erzwingt.

Ich möchte die Methode (Sequenz -> Sequenz) anstelle der Methode (Liste -> Sequenz) verwenden, um zu vermeiden, dass sich die gesamte Eingabeliste gleichzeitig im Speicher befindet.

Fragen:

1) Warum ist die erste Methode so langsam (und wird bei größeren Eingabelisten immer schlechter)? (Ich vermute, dass es mit der wiederholten Erstellung neuer Sequenzen mit Seq.skip 1 zu tun hat, aber ich bin mir nicht sicher)

2) Wie kann ich das Parcheando von Löchern in den Daten schnell machen, indem ich eine Eingabe Reihenfolge und nicht eine Eingabe Liste ?

Der Code:

open System

// Method 1 (Slow)
let insertDummyValuesWhereASingleValueIsMissing1 (timeBetweenContiguousValues : TimeSpan) (values : seq<(DateTime * float)>) =
    let sizeOfHolesToPatch = timeBetweenContiguousValues.Add timeBetweenContiguousValues // Only insert dummy-values when the gap is twice the normal
    (None, values) |> Seq.unfold (fun (prevValue, restOfValues) ->  
        if restOfValues |> Seq.isEmpty then
            None // Reached the end of the input seq
        else
            let currentValue = Seq.hd restOfValues
            if prevValue.IsNone then
                Some(currentValue, (Some(currentValue), Seq.skip 1 restOfValues  )) // Only happens to the first item in the seq
            else
                let currentTime = fst currentValue
                let prevTime = fst prevValue.Value
                let timeDiffBetweenPrevAndCurrentValue = currentTime.Subtract(prevTime)
                if timeDiffBetweenPrevAndCurrentValue = sizeOfHolesToPatch then
                    let dummyValue = (prevTime.Add timeBetweenContiguousValues, 42.0) // 42 is chosen here for obvious reasons, making this comment superfluous
                    Some(dummyValue, (Some(dummyValue), restOfValues))
                else
                    Some(currentValue, (Some(currentValue), Seq.skip 1 restOfValues))) // Either the two values were contiguous, or the gap between them was too large to patch

// Method 2 (Fast)
let insertDummyValuesWhereASingleValueIsMissing2 (timeBetweenContiguousValues : TimeSpan) (values : (DateTime * float) list) =
    let sizeOfHolesToPatch = timeBetweenContiguousValues.Add timeBetweenContiguousValues // Only insert dummy-values when the gap is twice the normal
    (None, values) |> Seq.unfold (fun (prevValue, restOfValues) ->  
        match restOfValues with
        | [] -> None // Reached the end of the input list
        | currentValue::restOfValues -> 
            if prevValue.IsNone then
                Some(currentValue, (Some(currentValue), restOfValues  )) // Only happens to the first item in the list
            else
                let currentTime = fst currentValue
                let prevTime = fst prevValue.Value
                let timeDiffBetweenPrevAndCurrentValue = currentTime.Subtract(prevTime)
                if timeDiffBetweenPrevAndCurrentValue = sizeOfHolesToPatch then
                    let dummyValue = (prevTime.Add timeBetweenContiguousValues, 42.0) 
                    Some(dummyValue, (Some(dummyValue), currentValue::restOfValues))
                else
                    Some(currentValue, (Some(currentValue), restOfValues))) // Either the two values were contiguous, or the gap between them was too large to patch

// Test data
let numbers = {1.0..10000.0}
let contiguousTimeStamps = seq { for n in numbers -> DateTime.Now.AddMinutes(n)}

let dataWithOccationalHoles = Seq.zip contiguousTimeStamps numbers |> Seq.filter (fun (dateTime, num) -> num % 77.0 <> 0.0) // Has a gap in the data every 77 items

let timeBetweenContiguousValues = (new TimeSpan(0,1,0))

// The fast sequence-patching (method 2)
dataWithOccationalHoles |> List.of_seq |> insertDummyValuesWhereASingleValueIsMissing2 timeBetweenContiguousValues |> Seq.iter (fun pair -> printfn "%f %s" (snd pair) ((fst pair).ToString()))

// The SLOOOOOOW sequence-patching (method 1)
dataWithOccationalHoles |> insertDummyValuesWhereASingleValueIsMissing1 timeBetweenContiguousValues |> Seq.iter (fun pair -> printfn "%f %s" (snd pair) ((fst pair).ToString()))

Answer 1

Jedes Mal, wenn Sie eine Sequenz mit Seq.hd y Seq.skip 1 tappt man mit ziemlicher Sicherheit in die Falle, O(N^2) zu verwenden. IEnumerable<T> ist ein hervorragender Typ für rekursive Algorithmen (einschließlich z. B. Seq.unfold ), da diese Algorithmen fast immer die Struktur "erstes Element" und "Rest der Elemente" haben und es keine effiziente Möglichkeit gibt, eine neue IEnumerable die den "Rest der Elemente" darstellt. ( IEnumerator<T> ist praktikabel, aber sein API-Programmiermodell ist nicht so einfach zu handhaben).

Wenn die Originaldaten "träge" bleiben sollen, sollten Sie eine LazyList (im F# PowerPack) verwenden. Wenn Sie die Faulheit nicht brauchen, sollten Sie einen konkreten Datentyp wie "list" verwenden, den Sie in O(1) "abschneiden" können.

(Sie sollten sich auch die Vermeidung von Stapelüberlauf (mit F# unendliche Sequenzen von Sequenzen) zu Ihrer Information, auch wenn es für dieses Problem nur am Rande relevant ist).

Answer 2

Seq.skip konstruiert eine neue Sequenz. Ich denke, das ist der Grund, warum Ihr ursprünglicher Ansatz langsam ist.

Ich neige zunächst dazu, einen Sequenzausdruck und Seq.pairwise zu verwenden. Das ist schnell und einfach zu lesen.

let insertDummyValuesWhereASingleValueIsMissingSeq (timeBetweenContiguousValues : TimeSpan) (values : seq<(DateTime * float)>) =
  let sizeOfHolesToPatch = timeBetweenContiguousValues.Add timeBetweenContiguousValues // Only insert dummy-values when the gap is twice the normal
  seq {
    yield Seq.hd values
    for ((prevTime, _), ((currentTime, _) as next)) in Seq.pairwise values do
      let timeDiffBetweenPrevAndCurrentValue = currentTime.Subtract(prevTime)
      if timeDiffBetweenPrevAndCurrentValue = sizeOfHolesToPatch then
        let dummyValue = (prevTime.Add timeBetweenContiguousValues, 42.0) // 42 is chosen here for obvious reasons, making this comment superfluous
        yield dummyValue
      yield next
  }