Dlaczego użycie sekwencji jest o wiele wolniejsze niż użycie listy w tym przykładzie?

Question

Tło: Mam sekwencję ciągłych, stempelkowanych danych. Sekwencja danych ma dziury, niektóre duże, inne tylko jedną brakującą wartość.
Ilekroć otwór jest tylko pojedynczą brakującą wartością, chcę załatać dziury za pomocą fałszywej wartości (większe dziury zostaną zignorowane).

Chciałbym użyć leniwego generowania poprawionej sekwencji, a tym samym używam Seq.unfold.

Wykonałem dwie wersje metody łatania otworów w danych.

Pierwszy zużywa sekwencję danych z otworów w nim i produkuje połatany sekwencję. To jest to, czego chcę, ale metody działają strasznie wolno, gdy liczba elementów w sekwencji wejściowej wzrośnie powyżej 1000, i stopniowo staje się coraz gorsza, im więcej elementów zawiera sekwencja wejściowa.

Druga metoda zużywa listy danych z otworami i produkuje połatany sekwencję i działa szybko. Nie jest to jednak to, czego chcę, ponieważ wymusza to utworzenie w pamięci całej listy danych wejściowych.

Chciałbym użyć metody (sekwencji -> sekwencji) zamiast metody (list -> sequence), aby w tej samej chwili nie mieć całej listy wejść w pamięci.

Pytania:

1) Dlaczego pierwsza metoda tak powoli (stopniowo coraz gorzej z większych list wejściowych) (jestem podejrzewać, że ma do czynienia z wielokrotnie tworzeniu nowych sekwencji z Seq.skip 1, ale nie jestem pewien)

2) w jaki sposób mogę dokonać łatanie dziur w danych szybko, podczas korzystania z wejścia sekwencję raczej niż wejściowego listy?

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

Answer 1

Seq.skip konstruuje nową sekwencję. Myślę, że właśnie dlatego twoje oryginalne podejście jest powolne.

Moja pierwsza skłonność to użycie wyrażenia sekwencji i Seq.pairwise. Jest to szybkie i łatwe do odczytania.

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 
    } 

Answer 2

każdym razem, gdy rozpadają się nast użyciu Seq.hd i Seq.skip 1 jesteś prawie na pewno wpadnięcia w pułapkę będzie O (n^2). IEnumerable<T> jest okropnym typem dla algorytmów rekursywnych (w tym np. Seq.unfold), ponieważ algorytmy te prawie zawsze mają strukturę "pierwszego elementu" i "pozostałej części elementów", i nie ma skutecznego sposobu na stworzenie nowego IEnumerable, który reprezentuje "pozostałość" elementów ". (IEnumerator<T> działa, ale jego model programowania API nie jest tak zabawny/łatwy w obsłudze).

Jeśli potrzebujesz oryginalnych danych, aby "zostać leniwym", powinieneś użyć LazyList (w F # PowerPack). Jeśli nie potrzebujesz lenistwa, powinieneś użyć konkretnego typu danych, takiego jak 'list', do którego możesz się "wciągnąć" w O (1).

(Należy również sprawdzić Avoiding stack overflow (with F# infinite sequences of sequences) jako FYI, choć to tylko stycznie dotyczy ten problem.)