Tło: Mam ciąg ciągłych danych ze znacznikami czasu. Sekwencja danych ma w niej dziury, niektóre duże, inne tylko jedną brakującą wartość.
Ilekroć dziura jest tylko jedną brakującą wartością, chcę załatać dziury używając wartości-atrapy (większe dziury zostaną zignorowane).

Chciałbym użyć leniwego generowania poprawionej sekwencji i dlatego używam Seq.unfold.

Zrobiłem dwie wersje metody, aby załatać dziury w danych.

Pierwszy zużywasekwencja danych z dziurami i tworzy łatanesekwencja. To jest to, czego chcę, ale metody działają strasznie powoli, gdy liczba elementów w sekwencji wejściowej wzrasta powyżej 1000 i staje się coraz gorsza, im więcej elementów zawiera sekwencja wejściowa.

Druga metoda zużywa alista danych z dziurami i tworzy łatanesekwencja i działa szybko. Nie jest to jednak to, czego chcę, ponieważ wymusza to utworzenie całej listy wejściowej w pamięci.

Chciałbym użyć metody (sekwencja -> sekwencja) zamiast metody (lista -> sekwencja), aby uniknąć jednoczesnego posiadania całej listy wejściowej w pamięci.

Pytania:

1) Dlaczego pierwsza metoda jest tak powolna (coraz gorzej z większymi listami wejściowymi) (podejrzewam, że ma to związek z wielokrotnym tworzeniem nowych sekwencji za pomocą Seq.skip 1, ale nie jestem pewien)

2) W jaki sposób mogę szybko wprowadzić poprawki w danych, korzystając z danych wejściowychsekwencja zamiast wkładulista?

Kod:

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